|
|
 | | From: | sytelus at yahoo.com | | Subject: | Quest For The Minimal Instruction Set | | Date: | 19 Jan 2005 22:13:10 -0800 |
|
|
 | Since past few years I've been pondering a question about what really
is the most minimal instruction set which will still qualify as a
Turing Machine. I think there must have been quite a research and
theaories around. If I think about modern computer processors, I can
easily see hat minimum instruction set a processor should have to be
Turing complete is,
1. If-Then test (A decision based branching instruction)
2. Memory copy
Above is assuming the program counter (which holds which memory
location has the instrution to execution next) itselt is accesible as
memory location.
Using just two instructions above, one can easily write a program, for
example, to add two numbers, logically XOR, do sum of first 100
integers.. and so on.
Recently I realised I don't need even (1).
That means, a processor just capable of doing Memory copy is a Turing
complete. If my theory is right, it has a huge impact for the theory
I'm developing for the instruction-memory equivalence and complexity of
logic machines.
My question is, according to current research what is the most minimal
instruction set? Does anybody have any pointers on Turing completeness
proof for the only memory copy capable machines?
Regards,
Shital.
http://www.ShitalShah.com
|
|
| | From: | Torben_Ęgidius_Mogensen | | Subject: | Re: Quest For The Minimal Instruction Set | | Date: | 20 Jan 2005 11:20:58 +0100 |
|
|
| sytelus@yahoo.com writes:
> Since past few years I've been pondering a question about what really
> is the most minimal instruction set which will still qualify as a
> Turing Machine. I think there must have been quite a research and
> theaories around. If I think about modern computer processors, I can
> easily see hat minimum instruction set a processor should have to be
> Turing complete is,
>
> 1. If-Then test (A decision based branching instruction)
> 2. Memory copy
>
> Above is assuming the program counter (which holds which memory
> location has the instrution to execution next) itselt is accesible as
> memory location.
>
> Using just two instructions above, one can easily write a program, for
> example, to add two numbers, logically XOR, do sum of first 100
> integers.. and so on.
>
> Recently I realised I don't need even (1).
>
> That means, a processor just capable of doing Memory copy is a Turing
> complete. If my theory is right, it has a huge impact for the theory
> I'm developing for the instruction-memory equivalence and complexity of
> logic machines.
>
> My question is, according to current research what is the most minimal
> instruction set? Does anybody have any pointers on Turing completeness
> proof for the only memory copy capable machines?
There are many "one-instruction machine"s around, for example one that
uses the instruction "reverse subtract and skip on 0". These machines
normally rely on the program being in writable memory, but not
necessarily the program counter, as you do.
That you need only a memory copy instruction in this case is not
really surprising, but I don't think I have seen it described (but
there is a lot of literature about the subject that I haven't read).
Computing only by memory copy is not really far away from what happens
in lambda calculus, where the basic operation is substituting a
variable by a value. Your machine is more low-level, as it operates
on machine addresses while lambda calculus works on trees (or graphs).
In any case, if your machine can store unbounded integers at each
location (which it needs to if you want to store addresses in memory
locations), you probably don't even need an unbounded number of
locations (it is well known that you can make a Turing-equivalent
machine with only two unbounded counters). So what you really should
investigate is the minimum number of locations required for your
machine to be Turing-complete.
Torben
|
|
|
