Jump to content

Talk:Turing machine examples

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

The 2-state 3-symbol TM was announced in Wolfram blog

[edit]

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.

"multiply" is "a problem that cannot be solved"???

[edit]

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]

State table confusion

[edit]

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 (talkcontribs) 23:21, 18 October 2008 (UTC)[reply]

List of References Missing

[edit]

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]