Tuesday, November 27, 2007

The smallest Turing machine ever

Read the details here.

Or check: the smallest computer in the world.

The first Universal Turing machine was defined by Alan Turing in 1936... here.

Oops! It seems that the proof of universality contains an error :>
Read here.


Andrea Valente said...

I'm reading about the R110 universal CA, but I cannot find an example how to use it...

How do you compute f(x)=x+1 with the R110 CA?

Some things about this are discussed here

And something else is presented here.

It could be nice to have a recipe to program the R110 machine :)

Andrea Valente said...

Here is an article that explains how to use CAs as language acceptors.

Still rather theoretical, but a step in the right direction: I'd like some examples of how to define a CA to implement a specific function.

Post a Comment