Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
scooping_the_loop_snooper [2019-09-13 08:31] – nik | scooping_the_loop_snooper [2019-09-13 08:34] (current) – loop snooping nik | ||
---|---|---|---|
Line 18: | Line 18: | ||
\\ | \\ | ||
You feed in your program, with suitable data,\\ | You feed in your program, with suitable data,\\ | ||
- | and P gets to work, and a little while later\\ | + | and //P// gets to work, and a little while later\\ |
(in finite compute time) correctly infers\\ | (in finite compute time) correctly infers\\ | ||
whether infinite looping behavior occurs.\\ | whether infinite looping behavior occurs.\\ | ||
\\ | \\ | ||
- | If there will be no looping, then P prints out ‘Good.’\\ | + | If there will be no looping, then //P// prints out ‘Good.’\\ |
That means work on this input will halt, as it should.\\ | That means work on this input will halt, as it should.\\ | ||
But if it detects an unstoppable loop,\\ | But if it detects an unstoppable loop,\\ | ||
- | then P reports ‘Bad!’ — which means you’re in the soup.\\ | + | then //P// reports ‘Bad!’ — which means you’re in the soup.\\ |
\\ | \\ | ||
- | Well, the truth is that P cannot possibly be,\\ | + | Well, the truth is that //P// cannot possibly be,\\ |
because if you wrote it and gave it to me,\\ | because if you wrote it and gave it to me,\\ | ||
I could use it to set up a logical bind\\ | I could use it to set up a logical bind\\ | ||
Line 34: | Line 34: | ||
Here’s the trick that I’ll use — and it’s simple to do.\\ | Here’s the trick that I’ll use — and it’s simple to do.\\ | ||
I’ll define a procedure, which I will call Q,\\ | I’ll define a procedure, which I will call Q,\\ | ||
- | that will use P’s predictions of halting success\\ | + | that will use //P//’s predictions of halting success\\ |
to stir up a terrible logical mess.\\ | to stir up a terrible logical mess.\\ | ||
\\ | \\ | ||
- | For a specified program, say A, one supplies, | + | For a specified program, say //A//, one supplies, |
- | the first step of this program called Q I devise\\ | + | the first step of this program called |
- | is to find out from P what’s the right thing to say\\ | + | is to find out from //P// what’s the right thing to say\\ |
- | of the looping behavior of A run on A.\\ | + | of the looping behavior of //A// run on //A.//\\ |
\\ | \\ | ||
- | If P’s answer is ‘Bad!’, Q will suddenly stop.\\ | + | If //P//’s answer is ‘Bad!’, |
- | But otherwise, Q will go back to the top,\\ | + | But otherwise, |
and start off again, looping endlessly back,\\ | and start off again, looping endlessly back,\\ | ||
till the universe dies and turns frozen and black.\\ | till the universe dies and turns frozen and black.\\ | ||
\\ | \\ | ||
- | And this program called Q wouldn’t stay on the shelf;\\ | + | And this program called |
I would ask it to forecast its run on itself.\\ | I would ask it to forecast its run on itself.\\ | ||
When it reads its own source code, just what will it do?\\ | When it reads its own source code, just what will it do?\\ | ||
- | What’s the looping behavior of Q run on Q?\\ | + | What’s the looping behavior of //Q// run on Q?\\ |
\\ | \\ | ||
- | If P warns of infinite loops, Q will quit;\\ | + | If //P// warns of infinite loops, |
- | yet P is supposed to speak truly of it!\\ | + | yet //P// is supposed to speak truly of it!\\ |
- | And if Q’s going to quit, then P should say ‘Good.’\\ | + | And if //Q//’s going to quit, then //P// should say ‘Good.’\\ |
- | Which makes Q start to loop! (P denied that it would.)\\ | + | Which makes //Q// start to loop! (P denied that it would.)\\ |
\\ | \\ | ||
- | No matter how P might perform, Q will scoop it:\\ | + | No matter how //P// might perform, |
- | Q uses P’s output to make P look stupid.\\ | + | //Q// uses //P//’s output to make //P// look stupid.\\ |
- | Whatever P says, it cannot predict Q:\\ | + | Whatever |
P is right when it’s wrong, and is false when it’s true!\\ | P is right when it’s wrong, and is false when it’s true!\\ | ||
\\ | \\ | ||
I’ve created a paradox, neat as can be —\\ | I’ve created a paradox, neat as can be —\\ | ||
- | and simply by using your putative P.\\ | + | and simply by using your putative |
- | When you posited P you stepped into a snare;\\ | + | When you posited |
Your assumption has led you right into my lair.\\ | Your assumption has led you right into my lair.\\ | ||
\\ | \\ | ||
So where can this argument possibly go?\\ | So where can this argument possibly go?\\ | ||
I don’t have to tell you; I’m sure you must know.\\ | I don’t have to tell you; I’m sure you must know.\\ | ||
- | A reductio: There cannot possibly be\\ | + | //A// reductio: There cannot possibly be\\ |
- | a procedure that acts like the mythical P.\\ | + | a procedure that acts like the mythical |
\\ | \\ | ||
You can never find general mechanical means\\ | You can never find general mechanical means\\ |