48
Turing asked the apparently simple question: could a computer program ever be written which would be able to look at any computer program and decide whether or not the program would stop in a finite amount of time?
Turing’s beautiful proof that this wasn’t possible was to argue as follows.
(i) Suppose such a program did exist, i.e. one which would be able to print either ‘It stops’ or ‘It doesn’t stop’ if shown any program (and then itself stop, presumably). (ii) Take this program and modify it slightly so that instead of printing ‘It stops’ when it sees a program which will stop, it instead goes into an infinite loop (such as in the first program above), otherwise printing ‘It doesn’t stop’ as before. (iii) Now show the program from (ii) to itself. The problem is that the program can’t determine that the program that it has just seen will stop – if it does this then it goes into an infinite loop and so the program does not stop. On the other hand, if the program thinks that the program it has seen won’t stop, then it prints ‘It doesn’t stop’ and then stops, contradicting the fact that it doesn’t stop. There is clearly a problem with (iii). The only place that the flaw seems to come from is the first step, i.e. (i), i.e. in assuming that there could be a program which could determine whether or not all programs stop. This is Turing’s famous result, akin to the liar paradox, i.e. the statement ‘this statement is false’, and Gödel’s incompleteness theorem showing that there will always be statements in Mathematics which be neither proved nor disproved, essentially by encoding the statement ‘this statement cannot be proved’. Chaitin takes Turing’s idea of halting and applies it to a number, creating the next digit in the number from the previous ones in such a way that one could never specify the information in any shorter form. This is his number Ω.
Back to Feinstein’s argument
So, the question is where this all leaves Feinstein’s argument regarding the Thwaites conjecture. The ideas behind the argument are based on Algorithmic Information Theory, which uses the word ‘random’ in a very specific sense, and which has produced some specific and apparently valid results.
The problem is partly that Feinstein’s article is so condensed that it is hard to see some of the steps clearly. My own feeling is that it in step (ii) of Feinstein’s
1 )( = nT k ,
argument that things go wrong. He states that ‘in order to prove that
)( nT k in the proof ’. There is no
it is necessary to specify the formula for
Made with FlippingBook - Online Brochure Maker