I was reading Charles Petzold's The Annotated Turing that walks through Turing's original proof out of curiosity and feel like I've missed something during the part where Turing is describing description numbers and standard descriptions. Specifically, to generalize what symbol an m-config will scan for as a number, Turing removes the ability to scan for "Any" that he used before.

I don't quite understand how this is possible without neutering the machine. To me, an m-config that scans for "Any", basically removing the effect of the scanned symbol entirely, is just not the same as an m-config that HAS to look for a specific symbol, or else crash the machine. While I can understand how it would work for some planned machines, I feel that if a Turing machine is chaotic enough there is no reasonable way to predict a scanned symbol, therefore needing to scan for "Any" to catch all possibilities. Can someone explain how Turing makes this claim?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.