This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computing This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing ??? This article has not yet received a rating on the project's importance scale. This article has been automatically rated by a bot or other tool as Stub-class because it uses a stub template. Please ensure the assessment is correct before removing the |auto= parameter.

I started this page, as per request. Will finish it soon. SamuelRiv 13:34, 6 November 2007 (UTC)Reply

Be wary with this page, as it is a common homework exercise for into computer science students. Therefore, I am not sure if I want to give a proof of Turing-completeness here (also I don't want to have to type it all out). Thoughts? SamuelRiv 13:34, 6 November 2007 (UTC)Reply

I could use help from somebody better at LaTeX than I: The transition arrows should look like (using notation from Kozen)

${\displaystyle {\begin{array}{c}1\\\rightarrow \\M\end{array}}~and~{\begin{array}{c}*\\\rightarrow \\M\end{array}}}$

Can somebody help to typeset this in a more elegant way? It should be just an arrow with a small "1" or "*" above and a small "M" below, and I'd like it to be able to format in-line. SamuelRiv 13:34, 6 November 2007 (UTC)Reply