A Turing Machine in the Classic Style | Hacker News Reader

A Turing Machine in the Classic Style

aturingmachine.com

96 pointsbockris24 comments

I really wish he hadn't used literal zero and one arabic numerals (along with blank) as his tape symbols.

dash and pipe would have been much more evocative of 1-bit information, rather than persisting with this misleading "ones and zeroes" bullshit that has infected popular culture and tends to totally obscure the underlying concept.

Thats very well put together. Great attention to detail with the user display as well.

I wonder how long it took to put together.

It's done by the guys at Parallax and the Propeller powers it:

http://en.wikipedia.org/wiki/Parallax_Propeller

Quite awesome, though I have to wonder how much computing power goes into reading the zero's and one's, controlling the servos, powering the led display, programs, etc. relative to the amount of computing power of the turing machine itself. A ratio of 10,000 to 1? A million to 1? A billion?

Isn't the whole point that they are equivalent? Both can calculate anything that can be calculated (in finite space, since both are limited by the finite length of the tape / size of RAM).

I immediately thought three things:

1) Cool! I want to clone it; baring time, I want to buy it.

2) Since I have neither time nor disposable income right now, I have some serious g33k envy.

3) Jay Walker's library should have this. (http://news.ycombinator.com/item?id=996939)

Well done, man.

That doesn't look like an infinite roll of paper tape to me.

It can, however, be arbitrarily long.

But even so, it's no more powerful than a finite state machine if the tape length is finite.

Turing machines don't define speed. So if the human is willing to get notified of a tape overrun, and splice on more tape, it is infinite.

Except that the computational capacity of the universe is finite (see http://arxiv.org/abs/quant-ph/0110141).

I remember that the Universal Turing machine needs an infinite tape. But I don't think you'd need one in practice.

Besides, memory and states in modern computers are finite too, and they're all Universal Turing machines.

I'd argue that our computers are no universal turing machines, but they surely are close enough for everyones needs. Just like the ocean is infinite if you try to swim through it, even though a plane crosses it in a few hours.

Not quite, in practice they are pretty much equivalent but they're not Universal Turing Machines. For that they would need to have infinite memory. A Universal Turing Machine is a theoretical construct, it's not something that could actually exist.

I did some more research and digging through my books.

A Universal Turing machine is one that can read programs from its own tape.

Infinite tapes are necessary for the halting problem, to allow programs to run infintely on infinite memory.

Turing Completeness is when the machine is proven to be equivalent to a Turing Machine, i.e. it can be programmed to solve any algorithmical problem.

Your definition is slightly wrong. In Alan Turing's own words:

    It is possible to invent a single machine which can be used
    to compute any computable sequence. If this machine I is
    supplied with a tape on the beginning of which is written the
    S.D of some computing machine M, {242} then I will compute
    the same sequence as M.

(Alan Turing, 1936, On Computable Numbers, With An Application To The Entscheidungsproblem)

So it is no merely that the Universal Machine can read and execute programs, it is that it can read and executes programs to make itself equivalent to ANY other turing machine. Thus the Universal Turing machine is Turing Complete. As the amount of tape required to solve all computable programs is unbounded the Universal Turing machine must have an infinitely long tape.

It's usually worth going straight to the source where you can in CS, but much more so with Turing as his papers are so nice and easy to read :)

right.

the tape only has to be $steps long, for $steps steps of computation, because that's the longest distance the head can travel at all.

any program that eventually halts, has a finite number of steps, so the band can be finite.

the only thing that requires an infinite band, is a non-halting program. and non-halting programs (unlike real-world servers and OSes) don't have a result as defined by the turing machine concept.

the only thing that requires an infinite band, is a non-halting program.

Sure, that's the only type of program that would use the whole tape, but given any tape of finite length, there's a (program, input) pair that needs a longer tape.

Pause machine, find new universe.

Does anyone have the original Turing paper? I missed the section about multi-core CPUs and SD cards.

This is very cool! Thanks for posting this link.

A very nice description of Turing machines, Abacus machines and in introduction to recursive functions can be found in the book "Computability and Logic" by Boolos, Burgess and Jeffrey.

"He further shows that a machine with the correct minimal set of operations can calculate anything that is computable, no matter the complexity."

Does anybody know what this principle is called?

There is the intuitive idea of an effectively computable function (of one or more natural numbers given as arguments): given the arguments, you can compute the value of the function using a "procedure" (or a set of rules) that does not require any creativity. Example: Addition of two natural numbers n and m. We know how to calculate n+m :-)

How can we formalize this notion of effective computability? On possible formalization is the notion of a Turing computable function, that means a function that can be computed by a Turing machine. One can show that addition, multiplication and many other functions can be computed by a Turing machine.

Now it is clear that every Turing computable function is effectively computable (just use pen and paper and write down what the Turing machine is doing).

The other direction is known as Church's Thesis (named after Alonzo Church) or Church-Turing-Thesis: every effectively computable function is Turing computable.

The thesis can not be proved, since "effectively computable" is an intuitive notion.

Two other formalizations of the notion of effectively computable are abacus computability (similar to Turing machines) and recursive functions. One can show that all these notions are equivalent.

http://en.wikipedia.org/wiki/Turing_complete

Reply on news.ycombinator.com