Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



Why would this distinction matter for the argument?


It 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).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: