Problem Detail: According to my understanding, a Turing machine that’s valid has to have finite steps to finish a certain step. If this is right, what else determines the validity of a turing machine?
Asked By : Shelby. S
Answered By : Jonathan Gallagher
If you are referring to what I think you are referring to then your understanding seems correct. A Turing machine has a precise definition: It is a tuple … see for example http://en.wikipedia.org/wiki/Turing_machine#Formal_definition Any system with the same components and conditions as described by the definition is indeed a Turing machine. Anything else (which may at first glance appear to be a Turing machine) is not a Turing machine. This distinction is to weed out some wrong intuitions.
Here is an example adopted from: http://stackoverflow.com/questions/2435607/why-is-this-an-invalid-turing-machine For example (given a polynomial P as input): Start counter at 0 Start Zero at False while(not Zero) { eval P(counter) if ^^ is 0 set Zero to True } Return True Can be computed by a Turing machine (i.e. describes a valid Turing machine) while Start list at [] Start counter at 0 while(true){ add eval P(counter) to list } if any element of list is 0 return true else return false Describes an invalid Turing machine, i.e. the code does not correspond to a Turing mahcine. Well ^^ is all I can come up with. Maybe it will help.
Here is an example adopted from: http://stackoverflow.com/questions/2435607/why-is-this-an-invalid-turing-machine For example (given a polynomial P as input): Start counter at 0 Start Zero at False while(not Zero) { eval P(counter) if ^^ is 0 set Zero to True } Return True Can be computed by a Turing machine (i.e. describes a valid Turing machine) while Start list at [] Start counter at 0 while(true){ add eval P(counter) to list } if any element of list is 0 return true else return false Describes an invalid Turing machine, i.e. the code does not correspond to a Turing mahcine. Well ^^ is all I can come up with. Maybe it will help.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11173
