4 ms·

Please correct me if I'm mistaken, but I did check a couple of years ago and found what I thought were some errors. I began to draft an email to you but never f

Please correct me if I'm mistaken, but I did check a couple of years ago and found what I thought were some errors. I began to draft an email to you but never finished and eventually discarded it. I'll try to recreate it here: With regards to halting, there are some programs that can be written simply in any common programming language to halt iff a solution to a specified number exists, simply by enumerating all possible values and halting if one satisfies the neccessary conditions. Thus to determine the halting of such a program would solve a problem. Typically these can be done in less than ten lines of Python, for instance. Some examples include: does there exist an odd perfect number; do there exist four positive integers a,b,c,n with n>2 such that a^n+b^n=c^n? The former is an open question; and the latter is Fermat's Last Theorem, which took an immense amount of machinery to prove, six decades after Turing's paper, and which is related to many open problems. (I've also heard that the halting problem could be used to solve the Riemann Hypothesis, but I don't know whether or not that's true.) If you can find a way to figure out whether or not such simple programs halt or not, I'd love to hear about it! What I've gleaned from your papers doesn't actually seem to apply to such programs though, which is a shame since these programs aren't very complicated. Now, with regards to Cantor, I recall reading a paper on your website (which I can't seem to find today, so apologies if I misrepresent it). I agree that set theory is not a good way to evaluate the number of numbers, since it throws out all properties about such numbers (e.g. ordering); this is why we have natural density, real density, and other properties. But there was another part where you indicated (something to the effect of) that the reals were countable since there are countably many Turing Machines; however I believe the correct conclusion to draw is that there are uncomputable numbers. Again, I can't seem to find it today, so I apologize if this is unsubstantiated.

EricHehner 6y ago
You point out quite correctly that if halting can be solved, then we can use it to settle certain open mathematical questions. But this does not tell us whether halting can be solved. (And if it can, it may not be a practical way to settle those questions.) I have many papers on the halting problem on my website at www.cs.utoronto.ca/~hehner/halting.html. The most recent is www.cs.utoronto.ca/~hehner/EGT+.pdf published in SN Computer Science v.1 p.308, 2020 September. Its final paragraph says: Let X and Y be two programming languages, or two computers, or two locations. It is inconsistent to ask for an X-program to compute halting for all X-programs due to a twisted self-reference. Twisted self-reference is characteristic of subjective specifications. So it may be consistent and satisfiable to ask for a Y-program to compute halting for all X-programs. At least it has not yet been proven impossible. If you want to know what a twisted self-reference is, or what a subjective specification is, you have to read the paper. This conclusion is not what you claimed it is. The Cantor paper you are unable to find is on my website. Its name is "the Size of a Set", and it is at www.cs.utoronto.ca/~hehner/SetSize.pdf. Its conclusion says: It is popularly believed that Cantor's diagonal argument proves that there are more reals than integers. In fact, it proves only that there is no onto function from the integers to the reals; by itself it says nothing about the sizes of sets. Set size measurement and comparison, like all mathematics, should be chosen to fit the needs of an application domain. For all application domains that I know of, Cantor's countability relation is not the most useful way to compare set sizes. I have never claimed, as you said, that there's anything wrong with Cantor's diagonal argument. My paper on Goedel, published in Beauty is our Business, Springer-Verlag silver series, New York, p.163-172, 1990, is at www.cs.utoronto.ca/~hehner/God.pdf. Nowhere in that paper is there any suggestion that "Goedel was wrong", as you claimed I said.
- PotatoPancakes 6y ago
  > So it may be consistent and satisfiable to ask for a Y-program to compute halting for all X-programs. At least it has not yet been proven impossible. Alas, it has been proven. RAM computers are equivalent to Turing machines. If X and Y are Turing-complete languages then all X-programs can be converted to Turing machines, your proposed Y-program can also be converted into a Turing machine. Put another way, unless your language X is too weak to be useful, there should exist a deterministic program to convert any program written in Y into a program written in X with identical behavior (with regard to halting). This should be evident by the fact that the computers we use day-in and day-out execute one binary machine language. Any X-program and Y-program reduce to the same assembly language. The twisted self-reference must therefore be language-agnostic. You can absolutely solve halting for various simplified "languages", but not Turing-complete languages.
  - PotatoPancakes 6y ago
    Here's a sketch of a proof explaining why this is impossible (under the Church-Turing thesis). Suppose you have written a Y-program y that takes an X-program x as input, and computes whether or not x halts (say, on no input), AND y halts every time. If X is a Turing-complete language, then for a given Turing Machine t we write an X-program xt that simulates t and halts iff t does. Then we run y on xt. This decides whether or not t halts, and works for all TMs t; therefore y solves the halting problem for all Turing Machines. But we know from Turing's "twisted self-reference" that no Turing Machine can do this, so the language Y must be strictly more computationally powerful than the Turing Machine model. This would disprove the Church-Turing thesis, which would be pretty incredible if true, but seems highly unlikely (since modern computers, and even quantum computers, are polynomial time equivalent to TMs). Otherwise, X is not a Turing-complete language. This is valid, I guess, but not really relevant to the problem of halting, since such a language would be very underpowered for most useful purposes. Now, regular languages are decidable, which is great for lots of computations that can be encoded using predicate logic and first-order arithmetic. Even climbing one rung up the computational complexity to context-free languages brings undecidability, though, since many problems (e.g. whether or not two context-free grammars generate the same language) are undecidable.

EricHehner 6y ago

You point out quite correctly that if halting can be solved, then we can use it to settle certain open mathematical questions. But this does not tell us whether halting can be solved. (And if it can, it may not be a practical way to settle those questions.) I have many papers on the halting problem on my website at www.cs.utoronto.ca/~hehner/halting.html. The most recent is www.cs.utoronto.ca/~hehner/EGT+.pdf published in SN Computer Science v.1 p.308, 2020 September. Its final paragraph says: Let X and Y be two programming languages, or two computers, or two locations. It is inconsistent to ask for an X-program to compute halting for all X-programs due to a twisted self-reference. Twisted self-reference is characteristic of subjective specifications. So it may be consistent and satisfiable to ask for a Y-program to compute halting for all X-programs. At least it has not yet been proven impossible. If you want to know what a twisted self-reference is, or what a subjective specification is, you have to read the paper. This conclusion is not what you claimed it is. The Cantor paper you are unable to find is on my website. Its name is "the Size of a Set", and it is at www.cs.utoronto.ca/~hehner/SetSize.pdf. Its conclusion says: It is popularly believed that Cantor's diagonal argument proves that there are more reals than integers. In fact, it proves only that there is no onto function from the integers to the reals; by itself it says nothing about the sizes of sets. Set size measurement and comparison, like all mathematics, should be chosen to fit the needs of an application domain. For all application domains that I know of, Cantor's countability relation is not the most useful way to compare set sizes. I have never claimed, as you said, that there's anything wrong with Cantor's diagonal argument. My paper on Goedel, published in Beauty is our Business, Springer-Verlag silver series, New York, p.163-172, 1990, is at www.cs.utoronto.ca/~hehner/God.pdf. Nowhere in that paper is there any suggestion that "Goedel was wrong", as you claimed I said.

PotatoPancakes 6y ago
> So it may be consistent and satisfiable to ask for a Y-program to compute halting for all X-programs. At least it has not yet been proven impossible. Alas, it has been proven. RAM computers are equivalent to Turing machines. If X and Y are Turing-complete languages then all X-programs can be converted to Turing machines, your proposed Y-program can also be converted into a Turing machine. Put another way, unless your language X is too weak to be useful, there should exist a deterministic program to convert any program written in Y into a program written in X with identical behavior (with regard to halting). This should be evident by the fact that the computers we use day-in and day-out execute one binary machine language. Any X-program and Y-program reduce to the same assembly language. The twisted self-reference must therefore be language-agnostic. You can absolutely solve halting for various simplified "languages", but not Turing-complete languages.
- PotatoPancakes 6y ago
  Here's a sketch of a proof explaining why this is impossible (under the Church-Turing thesis). Suppose you have written a Y-program y that takes an X-program x as input, and computes whether or not x halts (say, on no input), AND y halts every time. If X is a Turing-complete language, then for a given Turing Machine t we write an X-program xt that simulates t and halts iff t does. Then we run y on xt. This decides whether or not t halts, and works for all TMs t; therefore y solves the halting problem for all Turing Machines. But we know from Turing's "twisted self-reference" that no Turing Machine can do this, so the language Y must be strictly more computationally powerful than the Turing Machine model. This would disprove the Church-Turing thesis, which would be pretty incredible if true, but seems highly unlikely (since modern computers, and even quantum computers, are polynomial time equivalent to TMs). Otherwise, X is not a Turing-complete language. This is valid, I guess, but not really relevant to the problem of halting, since such a language would be very underpowered for most useful purposes. Now, regular languages are decidable, which is great for lots of computations that can be encoded using predicate logic and first-order arithmetic. Even climbing one rung up the computational complexity to context-free languages brings undecidability, though, since many problems (e.g. whether or not two context-free grammars generate the same language) are undecidable.