Content deleted Content added
m Link time-constructible function |
|||
Line 36:
Now if we feed [''N''] as input into ''N'' itself (which makes ''n'' the length of [''N'']) and ask the question whether ''N'' accepts its own description as input, we get:
* If ''N'' '''accepts''' [''N''] (which we know it does in at most ''f''(''n'') operations), this means that ''K'' '''rejects''' ([''N''], [''N'']), so ([''N''], [''N'']) is not in ''H<sub>f</sub>'', and thus ''N'' does not accept [''N''] in ''f''(''n'') steps. Contradiction!
* If ''N'' '''rejects''' [''N''] (which we know it does in at most ''f''(''n'') operations), this means that ''K'' '''accepts''' ([''N''], [''N'']), so ([''N''], [''N'']) '''is''' in ''H<sub>f</sub>'', and thus ''N'' '''does''' accept [''N''] in ''f''(''n'') steps. Contradiction!
We thus conclude that the machine ''K'' does not exist, and so
| |||