Definition talk:Turing Machine

From ProofWiki
Jump to navigation Jump to search

I've seen definitions like the one here in a few books, and it gets across the idea, but we might additionally want a more formal definition on this page that matches up with the description here. I'm bringing this up because the new Existence_of_Uncomputable_Functions page's proof is apparently hoping to link to a result that will essentially be a redefinition of Turing Machines that makes that proof easier.

So, question: do we want a formal definition on this page, or (in view of the fact that there's lots of things which are essentially equivalent to turing machines and could be called by the same name) do we want to have separate pages formally defining objects and justifying using them when we say "Turing machine" by verifying that they fit the informal description here?

Also, I feel like I should question the use of the word "algorithm(ic)" in the definition of a Turing machine (even informal), since part of the point of studying them is to get a formalized idea and understanding of algorithms. :D

-- Qedetc 17:57, 15 June 2011 (CDT)

Be a nice-to-have, perhaps (in that it leads us to the concept of "Turing-complete" computer languages (or whatever that malarkey is all about) but we already have a fairly comprehensive analysis of computability from the point of view of an Unlimited Register Machine. All we need to do is prove that a URM can be emulated by a Turing machine and we've done all we need. I do not think it's worth recreating the entire sequence of results from the point of view of a TM.
Besides, that Existence of Uncomputable Functions page has already been deleted. --prime mover 00:16, 16 June 2011 (CDT)
Ah, I see. I hadn't poked around much. With all the register machine stuff here it definitely seems like it would (if nothing else) be an inefficient way to spend time if one were to redo it all with Turing machines. -- Qedetc 00:41, 16 June 2011 (CDT)

Formal definition

Is the following formal definition acceptable?

A (deterministic) Turing machine is an ordered tuple

$ \displaystyle \left({ S, I, \Sigma, b, T }\right) $


  • $S$ is the set of states;
  • $I \in S$ is the initial state;
  • $\Sigma$ is the alphabet, the set of symbols permissible on the tape;
  • $b \in \Sigma$ is the blank symbol, the symbol which every cell on the tape is initialized to at the start;
  • $T : S \times \Sigma \to S \times \left({ \Sigma \cup \left\{ {L, R} \right\} }\right) $ (where $L,R \notin \Sigma$) is the transition function:
    • If $T \left({ s, \sigma }\right) = \left({ s', L }\right)$ for some $s'$, the head moves one cell to the left.
    • If $T \left({ s, \sigma }\right) = \left({ s', R }\right)$ for some $s'$, the head moves one cell to the right.
    • If $T \left({ s, \sigma }\right) = \left({ s', \sigma' }\right)$ for some $s'$, the symbol in the current cell is replaced with $\sigma'$.
    • In all three cases, the current state of the machine is set to $s'$.

This definition follows the informal description on the page. Personally, I learnt it differently. In my course, the transition function returned both a new symbol and a direction to move into, i.e. $T : S \times \Sigma \to S \times \Sigma \times \left\{ {L, R} \right\} $. — Timwi (talk) 14:29, 20 December 2012 (UTC)

In Arto Salomaa's 1973 book in $\S 4$ he defines it using a semi-Thue system allowing stationary motion of the head (what he termed overprinting). In Keijo Ruohonen's 2009 summary he defined it in $\S 6.1$ as a septuple in terms of his definition of an LBA (he also explicitly stated that the definition we are operating with was that of a deterministic Turing machine). I think we should go with your definition because it is closest to John C. Martin's 2010 introduction to the field (Definition $9.1$). It is contemporary, ideal for an introduction and is simpler (being a quintuple). The only modification I would make is $\{L,S,R\}$ ($S$ for stationary) instead of $\{L,R\}$. Just my opinion :) --Jshflynn (talk) 18:26, 20 December 2012 (UTC)
Excellent presentation. Suggest what we want to do here is have two sections "informal definition" and "formal definition". Really needs two subpages transcluded into this one as per normal - but I can do the refactoring once the page is up according to what you think it ought to say. Quote your source(s) carefully as there are several different treatments of this subject and there may be several different styles of presentation - we may want to include more than one, and it's a nice-to-have to be able to cite the source accurately and reliably. --prime mover (talk) 22:12, 20 December 2012 (UTC)
As for: "In my course, the transition function returned both a new symbol and a direction to move into, i.e. $T : S \times \Sigma \to S \times \Sigma \times \left\{ {L, R} \right\} $" yes, that looks okay to me, the informal presentation is just that - informal and possibly inaccurate / incomplete. --prime mover (talk) 22:22, 20 December 2012 (UTC)