Talk:Turing machine examples

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

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics 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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html?lid=title —Preceding unsigned comment added by 201.22.151.3 (talk) 03:34, 1 November 2007 (UTC)Reply

There is a debate about whether the proof is valid (see Talk:Wolfram's 2-state 3-symbol Turing machine#Universality proof disputed). Not only that, but the machine is quite complex and not suitable for this page anyway.

The statement

It is used in the "multiply" routine, "a problem that cannot be solved by any finite-state machine"

in the first paragraph of the copy subroutine section is completely confusing. Is appears to imply that multiplication cannot be performed using a finite T.M. which I believe is incorrect (I am not a computer theory scientist but otherwise it contradicts the very idea of a universal machine modeling real computers).

If in fact such a statement IS correct, it should be given somewhat more discussion and preferably a hyperlink to a wiki page with appropriate title (even if such page does not exist or a two-sentence stub page is created). This would both clarify that this is indeed what is meant and would address the natural disbelief.

If the above statement in bold is incorrect but such an incorrect judgement was actually made by Minsky, this should be clarified/specified.

If something else is meant, this should be explained as now it is completely misleading.

It would also be great to give a short informal definition of the "multiply" algorithm (or the corresponding problem) -- is it the problem of printing a product of two integers given those integers?

Yes, that is the multiply problem. It can obviously be done by Turing machines or any other universal machine. When Minsky said "finite-state machine" he probably meant a different, more limited model of computation (finite-state machine). But the quote was confusing so I removed it. — Carl (CBM · talk) 02:24, 22 August 2007 (UTC)Reply

I know it might not seem as logical on the face of it (which is why I am putting this here rather than just changing it), but it seems to me that the state tables should be in the order of the 5-tuple (state, letter, next state, next letter, direction). Asmeurer (talk ♬ contribs) 23:21, 18 October 2008 (UTC)Reply

There is no list of references in this article even though there are several references used. Bradburyist (talk) 17:40, 22 April 2009 (UTC)Reply

Actually, what's missing is any coherent exposition of the subject matter: sorry, but this whole article is gibberish. — Preceding unsigned comment added by 124.190.209.59 (talk) 19:07, 14 July 2013 (UTC)Reply