# What determines valid and invalid turing machines?

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?

• I am not familiar with the concept of valid Turing machines. Which textbook are you using? Is it something that was mentioned in class? Apr 9, 2013 at 23:27
• I'm using Introduction to the Theory of Computation by Michael Sipser, our professor mentioned validity, but the book doesn't mention validity much. Apr 9, 2013 at 23:29
• Perhaps you should ask the professor, then. Apr 9, 2013 at 23:42
• Are you sure you don't mean a valid encoding of a machine? Apr 9, 2013 at 23:42
• Yea, I asked him several times already, he wasn't very clear as his English isn't very good. So this is why I turned over to Stack exchange :( I'll try looking for more info. Apr 9, 2013 at 23:57

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: https://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.

• I honestly can't tell if this is the answer I'm looking for lol. I guess my conclusion by what my professor means by valid and invalid is if it's structured properly? Apr 10, 2013 at 22:11