Thread replies: 5
Thread images: 1
Thread images: 1
File: 20170608_155454.jpg (2MB, 3264x2448px) Image search:
[Google]
2MB, 3264x2448px
Is the Halting problem wrong? The proof is basically recursion: let halt(f(x)) output 1 if f(x) halts and 0 if it doesn't. You can make halt(halt(f(x)) which always yields 1 but you can't make halt(halt) because halt requires a parameter. Does this mean Godel was wrong too? Mind you that both men were crazy: Turing killed himself and Godel was a known schizophrenic who technically also killed himself.
Pic unrelated
>>
>>8964547
Gödel and Turing were right for similar reasons. It's not an inductive or recursive proof, it's a proof by contradiction.
You assume what you think is wrong (that halt(x) can be built and used) and then construct Decide(x) which is
if halt(x) => halt
then cause this machine to loop
if halt(x) == loop
then halt this machine
then run Decide(Decide)
if halt says decide loops, then decide halts.
if halt says decide halts, then decide loops.
A contradiction. Therefore halt(x) can't be built.
>>
>>8964880
There is a parameter missing when you said Decide(Decide(?)). Decide(f(x)) is the inverse if halt(f(x)). So that is why you are relying on recursion here, and as we learned with Russell of all people, recursion cannot be used like this. A machine halts or not with an input x, this is just damn obvious to me. Suppose you were to say halt(halt(f(x)), it would be okay, buy you can never say halt(x) without messing with the parameters.
>>
>>8964547
>The proof is basically recursion
this is where i stopped reading
>>
>>8966060
>this
stopped reading there
Thread posts: 5
Thread images: 1
Thread images: 1