-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.

|cite|improve this question
$\endgroup$

closed as off topic by Kaveh Nov 7 '12 at 14:57

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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).

|cite|improve this answer
$\endgroup$

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