5 ms·
Can someone explain this part of Turing's proof: > ... we can define an uncomputable problem like the one in Turing’s proof: “Given an input string representin
by ballenf 3y ago
Can someone explain this part of Turing's proof:
> ... we can define an uncomputable problem like the one in Turing’s proof: “Given an input string representing the code of an algorithm, output 1 if that algorithm outputs 0 when its own code is the input; otherwise, output 0.” Every algorithm that tries to solve this problem will produce the wrong output on at least one input — namely, the input corresponding to its own code.
Why is this impossible?
As I see it, there are two algorithms intermixed in that statement:
1. Code that emits a 0 if the input is it's own code
2. Code that emits a 1 if it receives as input code that behaves according to Algo 1.
Feel like I'm missing something basic or obvious!
- lsy 3y agodef unc(algstr) { if (algstr(algstr) == 0) return 1 else return 0 } unc(unc) -> what does this return?
- hyperhello 3y agoStack overflow exception, since it calls unc(unc) from itself.
- ghkbrew 3y agoImagine you have an code which does #2. Now give it itself as an argument. What is the result? If it emits 0 then it's behaving according to #1, then because we assumed it satisfies #2 it must emit 1, a contradiction. Similarly it can't emit 1. Thus it is impossible to have an algorithm which solves #2 for all inputs, because it must fail on at least one input (itself)
- deleted 3y ago[deleted]