3 ms·

> 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, i

> 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

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.