[Solved]: What determines valid and invalid turing machines?

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11173