Email or username:

Password:

Forgot your password?
Top-level
leah & asm & forth, oh my!

@neauoire

>

With universal machines, they explained why it’s impossible to decide if a given Turing machine ever halts

NO. NO THEY DIDN'T. :blobscream:​ see my pinned posts!​

2 comments
Devil Lu Linvega

@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?

leah & asm & forth, oh my!

@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

   p(function f) {
if halts(f) {
while(1);
} else {
return 0;
}
halts(p);

@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

Go Up