-3
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ downvotes without comments. annoying $\endgroup$ – RParadox Oct 19 '12 at 15:25
  • 1
    $\begingroup$ cstheory is for research level questions (see 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. $\endgroup$ – Marzio De Biasi Oct 19 '12 at 19:06
  • $\begingroup$ 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 Computer Science which has a broader scope. $\endgroup$ – Kaveh Oct 19 '12 at 19:22
  • 1
    $\begingroup$ downvotes without comments are just as annoying as out-of-scope questions without reading FAQ. $\endgroup$ – Artem Kaznatcheev♦ Oct 28 '12 at 0:27
  • 1
    $\begingroup$ 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. $\endgroup$ – RParadox Oct 28 '12 at 0:30
3
$\begingroup$

Look at the " $U$s " in the first table of the paper "Small Turing Machines ...". 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

From Wikipedia: ... The RASP is a random-access machine (RAM) model 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" (they use a larger ALGOL-like set of instructions).

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.