Talk:Turing machine examples

From Wikipedia, the free encyclopedia

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

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)

[edit] "multiply" is "a problem that cannot be solved"???

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)