The Minsky Machine
I've said before that all computing systems are ultimately equivalent. This is something known as the Church-Turing thesis. It's interesting to look at one or two machines other than the Turing machine, just to get some idea of why we believe that, and what other computers might look like.
There's a really fun computing machine designed by Marvin Minsky, an incredibly smart and prolific computer scientist. He just called them "program machines" when he first proposed them; most of us call them "Minsky Machines". I really like Minsky machines; I find their programs much easier to read and write than Turing machine programs, and their behavior is closer to real computers.
The minsky machine is astoundingly simple: even simpler than the turing machine. A minsky machine consists of:
Here's a subtraction program for a minsky machine with two registers. It takes two numbers in registers A and B, and leaves the result in A. If it halts with anything but 0 in B, then it's an error.
First, it decrements the value in register B; if B is zero, then the subtraction is done, so it jumps to halt. If B is greater than 0, then it subtracts one from B, and then tries to subtract one from A. If A is already zero, then it adds one to B (to be sure that B != 0) and halts. If A isn't zero, then it decrements it, and goes back to the beginning.
Now, here's a question: is this really equivalent to a turing machine? Intuitively, you can problably get a sense that this is a complete effective computing system. But how do we prove it?
Well, we know that a two-stack push-down automaton is completely equivalent to a turing machine: the two stacks can simulate the parts of the tape on either side of the head. And we know that if something can be done with a turing machine, it can be done with a binary (two symbol) turing machine. So - we need to show that we can simulate a two-stack binary push-down automaton using a minsky machine. A pushdown automaton is really just a FSM with two stacks.
Since we already showed we can implement fully general natural number subtraction with a Minsky machine, we know that we can implement an FSM: subtraction is strictly harder than anything an FSM can do - so if our machine can implement a general subtraction, it can implement an FSM. So what we need to do is show that we can implement the stacks.
And that's easy. Here's how you implement a stack with two registers: one register holds a binary number. That binary number is the stack. To push a value on the stack, you multiply by two, and add the value. To pop the value on top of the stack, you take divide by two; the result of the division is the popped stack, and the remainder is the value that was on top. So you've got the stack data in one register. You need a second register to use to implement the multiplications and divisions.
So, if you've got four registers, then you've got two stacks. Poof. You've got a turing machine.
Going the other direction, it should be pretty easy to see how to implement a Minsky machine with a turing machine. To make things easy, we can use a multi-tape turing machine (since we know that that's no more powerful than a one-tape). Each register is one tape, containing its value in unary; and one tape contains the program.
There's a really fun computing machine designed by Marvin Minsky, an incredibly smart and prolific computer scientist. He just called them "program machines" when he first proposed them; most of us call them "Minsky Machines". I really like Minsky machines; I find their programs much easier to read and write than Turing machine programs, and their behavior is closer to real computers.
The minsky machine is astoundingly simple: even simpler than the turing machine. A minsky machine consists of:
- A finite set of registers, A, B, C, ..., each of which contains a natural number.
- A list of numbered instructions.
- Increment: increment takes two parameters: a register, and an instruction number. It increments the value stored in the specified register, and then jumps to the instruction at the number.
- Decrement: decrement takes three parameters: a register, and two instruction numbers. If the value in the register is 0, it jumps to the instruction at the first number; if the value in the register is greater than zero, it decrements it, and jumps to the instruction at the second number.
- Halt.
Here's a subtraction program for a minsky machine with two registers. It takes two numbers in registers A and B, and leaves the result in A. If it halts with anything but 0 in B, then it's an error.
1: Decrement(B, 4, 2)
2: Decrement(A, 3, 1)
3: Incr(B,4)
4: Halt
First, it decrements the value in register B; if B is zero, then the subtraction is done, so it jumps to halt. If B is greater than 0, then it subtracts one from B, and then tries to subtract one from A. If A is already zero, then it adds one to B (to be sure that B != 0) and halts. If A isn't zero, then it decrements it, and goes back to the beginning.
Now, here's a question: is this really equivalent to a turing machine? Intuitively, you can problably get a sense that this is a complete effective computing system. But how do we prove it?
Well, we know that a two-stack push-down automaton is completely equivalent to a turing machine: the two stacks can simulate the parts of the tape on either side of the head. And we know that if something can be done with a turing machine, it can be done with a binary (two symbol) turing machine. So - we need to show that we can simulate a two-stack binary push-down automaton using a minsky machine. A pushdown automaton is really just a FSM with two stacks.
Since we already showed we can implement fully general natural number subtraction with a Minsky machine, we know that we can implement an FSM: subtraction is strictly harder than anything an FSM can do - so if our machine can implement a general subtraction, it can implement an FSM. So what we need to do is show that we can implement the stacks.
And that's easy. Here's how you implement a stack with two registers: one register holds a binary number. That binary number is the stack. To push a value on the stack, you multiply by two, and add the value. To pop the value on top of the stack, you take divide by two; the result of the division is the popped stack, and the remainder is the value that was on top. So you've got the stack data in one register. You need a second register to use to implement the multiplications and divisions.
So, if you've got four registers, then you've got two stacks. Poof. You've got a turing machine.
Going the other direction, it should be pretty easy to see how to implement a Minsky machine with a turing machine. To make things easy, we can use a multi-tape turing machine (since we know that that's no more powerful than a one-tape). Each register is one tape, containing its value in unary; and one tape contains the program.
posted by MarkCC at
11:48 AM
RSS
6 Comments:
@thomas:
Not any more than the trailing zeros on the number 1000 contract to zero, or the number 1111 condenses down to 1. ;-)
Imagine back when you were at primary school (or elementary or whatever you call it in your part of the world) when you learned about "hundreds" and "tens" and "units". If you look at it closely, the "units" in decimal system are 10^0; the tens are 10^1; and the hundreds 10^2. You can see the power changes but the base doesn't. If you change the base to - for example - binary (ie, 2) then the columns and corresponding numbers become:
8: 2^3
4: 2^2
2: 2^1
1: 2^0
It becomes obvious that finding out the number system in a new base is as simple as changing the B in B^N. For a unary (ie, base 1) system we get:
1: 1^3
1: 1^2
1: 1^1
1: 1^0
In a decimal system
10^3 + 10^1 + 10^0 = 1000 + 10 + 1 = 1011
and in a unary system
1^3 + 1^1 + 1^0 = 1 + 1 + 1 = 111 (base 1) or 3 (base 10)
I hope all that made sense! :)
By
Anonymous, at 1:57 PM
Your subtraction program appears to produce 1 - 1 = 1.
A = 1
B = 1
Decrement B
B = 0
Halt
By
Anonymous, at 2:09 PM
My mistake -- I see now that the test for zero is prior to the actual decrement.
By
Anonymous, at 2:10 PM
ithika:
Thanks; I was working on writing up almost the exact same explanation :-)
bmurray:
Decrement *first* checks if the register contains zero; if it does, it branches to the first instruction; if it doesn't, then it decrements and branches to the second. So when b=1, it decrements b and branches to the instruction to decrement a. So you'd see the sequence:
B=1,A=1 (now do decrement B)
B=0,A=1 (now do decrement A)
B=0,A=0 (now do decrement B
Halt.
By
MarkCC, at 2:15 PM
Actually I think Thomas' misapprehension is based on something different: the idea that the set of symbols used in numbering systems necessarily begins with a zero, complete with all the zero-like properties it has in binary and higher systems.
The difference is, in a unary system there is no need to indicate absence. That is, zero with zero-like properties has no use. Consequently the best symbolic mapping of digits to a unary system would be to use 1 as the sole symbol in the system. Practically, however, unary requires a single symbol and its only indication is the presence of a single instance. The shape of the symbol is irrelevant.
By
Anonymous, at 2:49 PM
It's quite unfortunate that our base system is not more intuitively named, but it actually represents a polynomial series typically. The names "unary" and "binary" represent the number of symbols available for notation (besides the helix point, but there is no helix point in unary anyway). To say a number is in base polynomial_n (or simply p_n) would be more descriptive notation, and would be more sound for different number notations.
By
Anonymous, at 7:35 PM
Post a Comment
<< Home