@millihertz the pinned post reads like Chatin's definition of the halting problem, which is also how I understood, isn't what Ben Lynn is describing?
Top-level
@millihertz the pinned post reads like Chatin's definition of the halting problem, which is also how I understood, isn't what Ben Lynn is describing? 1 comment
|
@neauoire no. the key bit he gets wrong is "a given Turing machine". what the Halting Problem says is that it's impossible to construct a universal function that says whether any arbitrary program will halt, and to prove this, postulates that such a function - halts(x) - has been found, and asks what will happen when we call
@neauoire no. the key bit he gets wrong is "a given Turing machine". what the Halting Problem says is that it's impossible to construct a universal function that says whether any arbitrary program will halt, and to prove this, postulates that such a function - halts(x) - has been found, and asks what will happen when we call