5 ms·

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

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.
PotatoPancakes 6y ago
Regarding Goedel, I apologize and retract my claim. Regarding Cantor, indeed, there are many ways to compare the "sizes" of two sets. Cardinality is one such way. It can have applications, for instance Cantor's original paper used it to prove that there are infinitely many transcendental numbers. It is also used in real analysis, in Lebesgue integration, and in measure theory. But it is not the only way to do so. There is a very real sense in which {1,2,3} is a smaller set than {4,5}; that does depend on knowledge of the contents of the set though, not merely the number of elements contained. In a more abstract context where measure or natural density aren't applicable, cardinality can be left as the only well-defined definition of "size", but in most contexts I agree, it's just one of many possible definitions and they should each be used with care. Arguing about the sizes of different infinite sets is tricky, though. The set of even integers has the same cardinality as the set of all integers, even though it has density 0.5. The cardinality of the set of rationals is somehow "infinitely less" than the set of irrationals, even though both sets are dense on one another. But there are some things we can learn from not having Me, however, I like cardinality for the aesthetic properties. I like the Axiom of Choice and all the nonsense that follows from it. Cardinal infinities behave quite differently from the well-defined infinities of ordinals, hyperreal numbers, and surreal numbers. In your article "The Size of a Set", you discuss Formalism. Are you aware of the axiom "V=L"? It's quite neat, because by effectively outlawing any non-constructible sets, the Generalized Continuum Hypothesis follows! If you accept cardinality as a purely aesthetic definition in conjunction with Formalist ideology, you get a very beautiful result. Practical, maybe not, but beautiful. That is all to say that I agree with a lot of what's in your paper on "the Size of a Set". However, the "Program Analogy" section of the paper contains what I think is a flawed argument: > [A] Cantor-type conclusion concerning the sizes of sets of programs is absurd. The proper conclusion is simply that there is no program (in some programming language) to generate all and only the infinite-sequence programs (in that same programming language). It is not a conclusion about the sizes of sets. Likewise in the original Cantor argument, the proper conclusion is not about the sizes of sets; it is simply that there is no sequence of all infinite sequences. I think the correct conclusion here is that to determine which programs are "infinite-sequence" is undecidable. You've reached a contradiction, therefore the last assumption must be flawed; in this case the assumption was that you could write a program D "whose execution neither halts nor goes into a non-printing infinite loop." This assumption is about programs and programming languages, and says nothing about sets, so the analogy is flawed. In Cantor's argument, the assumption is that the set [0,1) can be ordered. You're correct in saying that this is merely a statement about the existence of a bijection between the naturals and the reals, but that is the definition of cardinality. Your issue here is that you don't like saying that cardinality means "size", and that's fair. But I think this analogy is a stretch at best, and irrelevant to your overall argument.

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.

PotatoPancakes 6y ago

Regarding Goedel, I apologize and retract my claim. Regarding Cantor, indeed, there are many ways to compare the "sizes" of two sets. Cardinality is one such way. It can have applications, for instance Cantor's original paper used it to prove that there are infinitely many transcendental numbers. It is also used in real analysis, in Lebesgue integration, and in measure theory. But it is not the only way to do so. There is a very real sense in which {1,2,3} is a smaller set than {4,5}; that does depend on knowledge of the contents of the set though, not merely the number of elements contained. In a more abstract context where measure or natural density aren't applicable, cardinality can be left as the only well-defined definition of "size", but in most contexts I agree, it's just one of many possible definitions and they should each be used with care. Arguing about the sizes of different infinite sets is tricky, though. The set of even integers has the same cardinality as the set of all integers, even though it has density 0.5. The cardinality of the set of rationals is somehow "infinitely less" than the set of irrationals, even though both sets are dense on one another. But there are some things we can learn from not having Me, however, I like cardinality for the aesthetic properties. I like the Axiom of Choice and all the nonsense that follows from it. Cardinal infinities behave quite differently from the well-defined infinities of ordinals, hyperreal numbers, and surreal numbers. In your article "The Size of a Set", you discuss Formalism. Are you aware of the axiom "V=L"? It's quite neat, because by effectively outlawing any non-constructible sets, the Generalized Continuum Hypothesis follows! If you accept cardinality as a purely aesthetic definition in conjunction with Formalist ideology, you get a very beautiful result. Practical, maybe not, but beautiful. That is all to say that I agree with a lot of what's in your paper on "the Size of a Set". However, the "Program Analogy" section of the paper contains what I think is a flawed argument: > [A] Cantor-type conclusion concerning the sizes of sets of programs is absurd. The proper conclusion is simply that there is no program (in some programming language) to generate all and only the infinite-sequence programs (in that same programming language). It is not a conclusion about the sizes of sets. Likewise in the original Cantor argument, the proper conclusion is not about the sizes of sets; it is simply that there is no sequence of all infinite sequences. I think the correct conclusion here is that to determine which programs are "infinite-sequence" is undecidable. You've reached a contradiction, therefore the last assumption must be flawed; in this case the assumption was that you could write a program D "whose execution neither halts nor goes into a non-printing infinite loop." This assumption is about programs and programming languages, and says nothing about sets, so the analogy is flawed. In Cantor's argument, the assumption is that the set [0,1) can be ordered. You're correct in saying that this is merely a statement about the existence of a bijection between the naturals and the reals, but that is the definition of cardinality. Your issue here is that you don't like saying that cardinality means "size", and that's fair. But I think this analogy is a stretch at best, and irrelevant to your overall argument.