3 ms·
The author uses "implement halts using X" in the sense of reducing the halting problem to the problem of X (technically, using Turing reduction). Not in the se
by tromp 4y ago
The author uses "implement halts using X" in the sense of reducing the halting problem to the problem of X (technically, using Turing reduction).
Not in the sense of solving the halting problem with a function which has an occurrence of X.
- Gehinnn 4y agoWhy would this distinction matter for the argument?
- dellamonica 4y agoIt does not matter at a high level but I think the distinction is that there should be only one black box in the proof, which is precisely the thing being reduced. Every other instruction/call used n the algorithm must be known to be computable (in this case, addition).