<p>Look at the " $U$s " in the first table of the paper "<a href="http://www.dm.unito.it/~cerruti/ac/paperpm1.pdf" rel="nofollow">Small Turing Machines ...</a>". For example, 2 states and 18 symbols are enough to build a Turing Machine that can execute an operating system (if you augment it with an adequate I/O mechanism :) ...</p>

<p>If you look for small models closer to the Von Neumann architecture then take a look at <a href="http://en.wikipedia.org/wiki/Random-access_stored-program_machine" rel="nofollow">Random-access stored-program machines</a></p>

<p>From Wikipedia: <em>... The RASP is a <a href="http://en.wikipedia.org/wiki/Random-access_machine" rel="nofollow">random-access machine (RAM) model</a> that, unlike the RAM, has its program in its "registers" together with its input....</em></p>

<p>The instruction set has only 3 opcodes: INC, DEC and JZ</p>

<p>See also <a href="http://www.cs.utoronto.ca/~sacook/homepage/rams.pdf" rel="nofollow">S.A. Cook and R.A. Reckhow, "Time Bounded Random Access Machines"</a> (they use a larger ALGOL-like set of instructions).</p>

CC BY-SA 3.0
2012-10-19T10:05:59.910Z
2012-10-19T10:30:22.733Z
2012-10-19T10:30:22.733Z
Marzio De Biasi
<p>I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a TM is that when the head reaches the end of the tape, a separate state is triggered: 'end of tape left' and 'end of tape right'. </p>

<p>Now, my experimental idea is to have the transition table in memory so that I have a more "complete" virtual machine, along the lines of a Von Neumann Universal Constructor (not quite the same). What is the minimal program that can run other programs in memory? I'm interested in a different structure of a minimal computing machine, where the transition table is closer to a machine instruction set and can be hold in memory. This will certainly bloat the structure - I'm fine with that. This would be something like a minimal machine which implements an operating system.</p>

CC BY-SA 3.0
2012-10-28T00:27:38.717Z
downvotes without comments are just as annoying as out-of-scope questions without reading [FAQ].
Artem Kaznatcheev
CC BY-SA 3.0
2012-10-28T00:30:39.243Z
Now I remember why I left academia. Who defines what research is? No thanks. Probably a good reason why research and the internet often don't connect. Goodbye.
RParadox
CC BY-SA 3.0
2012-10-19T15:25:06.340Z
downvotes without comments. annoying
RParadox
CC BY-SA 3.0
2012-10-19T19:06:46.713Z
cstheory is for research level questions (see [FAQ](http://cstheory.stackexchange.com/faq) ), cs.stackexchange.com should be the correct site for questions like this. And answering to it, I exposed myself to (deserverd) downvotes, too :-) :-), but a few days ago I finally understood the details of Rogozinh's 2 states 18 symbols UTM ... so I zestful answered to your question.
Marzio De Biasi
CC BY-SA 3.0
2012-10-19T19:22:47.520Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. The questions seems more suitable for [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2012-10-19T19:24:50.997Z
PS: users are not required to explain their down-votes on cstheory. Often reading the [FAQ] can help you find out the reason for the down-vote.
Kaveh
<computability><automata-theory><turing-machines><machine-models><cellular-automata>
Minimal Turing Machine implementation / Von Neumann UC
RParadox
# Minimal Turing Machine implementation / Von Neumann UC

(Asked by: username_0 on 2012-10-19)

I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a TM is that when the head reaches the end of the tape, a separate state is triggered: 'end of tape left' and 'end of tape right'.

Now, my experimental idea is to have the transition table in memory so that I have a more "complete" virtual machine, along the lines of a Von Neumann Universal Constructor (not quite the same). What is the minimal program that can run other programs in memory? I'm interested in a different structure of a minimal computing machine, where the transition table is closer to a machine instruction set and can be hold in memory. This will certainly bloat the structure - I'm fine with that. This would be something like a minimal machine which implements an operating system.

**Tags:** computability, automata-theory, turing-machines, machine-models, cellular-automata

> **Comments:**
> **username_0**: downvotes without comments. annoying  
> **username_2**: cstheory is for research level questions (see [FAQ](http://cstheory.stackexchange.com/faq) ), cs.stackexchange.com should be the correct site for questions like this. And answering to it, I exposed myself to (deserverd) downvotes, too :-) :-), but a few days ago I finally understood the details of Rogozinh's 2 states 18 symbols UTM ... so I zestful answered to your question.  
> **username_3**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. The questions seems more suitable for [cs.se] which has a broader scope.  
> **username_3**: PS: users are not required to explain their down-votes on cstheory. Often reading the [FAQ] can help you find out the reason for the down-vote.  
> **username_1**: downvotes without comments are just as annoying as out-of-scope questions without reading [FAQ].  
> **username_0**: Now I remember why I left academia. Who defines what research is? No thanks. Probably a good reason why research and the internet often don't connect. Goodbye.  

---

## 1 answers

### Answer by username_2 on 2012-10-19. Score: 3 | Accepted answer

Look at the " $U$s " in the first table of the paper "[Small Turing Machines ...](http://www.dm.unito.it/~cerruti/ac/paperpm1.pdf)". For example, 2 states and 18 symbols are enough to build a Turing Machine that can execute an operating system (if you augment it with an adequate I/O mechanism :) ...

If you look for small models closer to the Von Neumann architecture then take a look at [Random-access stored-program machines](http://en.wikipedia.org/wiki/Random-access_stored-program_machine)

From Wikipedia: *... The RASP is a [random-access machine (RAM) model](http://en.wikipedia.org/wiki/Random-access_machine) that, unlike the RAM, has its program in its "registers" together with its input....*

The instruction set has only 3 opcodes: INC, DEC and JZ

See also [S.A. Cook and R.A. Reckhow, "Time Bounded Random Access Machines"](http://www.cs.utoronto.ca/~sacook/homepage/rams.pdf) (they use a larger ALGOL-like set of instructions).


---

