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?

  • $\begingroup$ I am not familiar with the concept of valid Turing machines. Which textbook are you using? Is it something that was mentioned in class? $\endgroup$ Apr 9, 2013 at 23:27
  • $\begingroup$ I'm using Introduction to the Theory of Computation by Michael Sipser, our professor mentioned validity, but the book doesn't mention validity much. $\endgroup$
    – Shelby. S
    Apr 9, 2013 at 23:29
  • $\begingroup$ Perhaps you should ask the professor, then. $\endgroup$ Apr 9, 2013 at 23:42
  • $\begingroup$ Are you sure you don't mean a valid encoding of a machine? $\endgroup$
    – Ran G.
    Apr 9, 2013 at 23:42
  • $\begingroup$ 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. $\endgroup$
    – Shelby. S
    Apr 9, 2013 at 23:57

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – Shelby. S
    Apr 10, 2013 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.