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\\ | ||
nik