OSDev.org

Hi there.

Some of you may remember me as the "asking way too may odd questions" guy. I've been away for a while, but now I've got a question that I think only you, the clever dudes and dudettes at this forum, can answer satisfactory.

Basically a buddy of mine is rather trying to force me into building a computer with him in minecraft and I don't really feel like taking part in such a large project, so the question arose. How simple can it actually be done?

I mean to add, subtract, multiply and divide and much more, you really only need AND XOR and LSL, or something along those lines.

Sure it wouldn't be the world fastest ALU, but it doesn't need to be. The only rule is that it can't have any limitations other than such things as speed, memory, number of registers, etc.

I've been searching far and wide, as I'm quite certain that I'm not the first to ask this question, but obviously didn't find anything of use to me. I did find something about a universal Turing machine, which involved at proof of how simple it could get, but I really didn't understand it.


So here goes, pressing the "Submit" button now. Hope you don't mind me bothering you all once again.

Maybe this is helpful to you: http://en.wikipedia.org/wiki/One_instru ... t_computer.

What I've been taught in uni is that the von Neumann architecture is a “hardware minimal” implementation. If you don't know, such CPUs have one register only (besides the instruction pointer), being the accumulator. Every arithmetic instruction combines that accu and a value taken from an arbitrary memory location (which is given as an immediate operand). Of course, there are also load/store and branching instructions.

I guess the main problem with both of these designs is that they both require you to have a sufficient amount of memory, and I can imagine building that in Minecraft being probably the hardest part about it.

Here's a picture:


Just a joke. The simplest logic based computer, in my opinion, would be one which has one single bit register. For addition, NOT it. For subtraction, NOT it. for multiplication, AND the register with either 1 or 0, depending on the button pressed. For division, not sure.

Hi,

There's a list of primitive operations that we're all used to. It's only about 20 operations:

• copy/assignment
  and
  or
  xor
  not
  add
  subtract
  negate
  multiply
  divide
  modulo
  shift left
  shift right
  push
  pop
  call
  return
  jump/goto
  conditional branch

These primitive operations are combined to do more complex operations. For example "if(x < y)" would be a subtraction and a branch.

In the same way, most of the primitive operations can done by other primitive operations. For example, "not" can be done with "xor", "negate" can be done with subtraction, multiplication can be done by repeated "shift and add", division (and modulo) can be done by repeated "shift and subtract", jump/goto can be done with copy/assignment (copy value into instruction pointer). This gives a "more minimal" list of operations like this:

• copy/assignment
  and
  or
  xor
  add
  subtract
  shift left
  shift right
  push
  pop
  call
  return
  conditional branch

Now; call and return are mostly the same as pushing and popping (e.g. push instruction pointer; pop instruction pointer). Pushing and popping can be done by using copy/assignment and addition or subtraction (copy something to stack top, then subtract the size from the stack pointer). Addition can be done with subtraction (e.g. "x = y + z" is the same as "x = y - (0 - z)". Shifting left can be done with addition (e.g. "x << 1" is the same as "x + x"). Shifting right can be done by shifting left with wrap around (e.g. "shr al,3" is the same as "rol al,8-3; and al,0x1F"). This gives us an "even more minimal" list:

• copy/assignment
  and
  or
  xor
  subtract
  conditional branch

Copy/assignment can be done with xor (e.g. "x = y" is the same as "x = x ^ 0; x = x ^ y"). If you have a look at De Morgan's laws you'll see that AND and OR can be done with XOR. For 2's complement, XOR can be done with "subtract then add 1". This gives us an "even more minimal" list:

• subtract
  conditional branch

This list can't be reduced further; but it's only 2 operations, and it's all you need to do everything.

Of course you'd need to add addressing modes on top of this (minimum would probably be "register, immediate operand, value at address in register and value at immediate address" - e.g. "mov eax,eax", "mov eax,0x1234", "mov eax,[eax]" and "mov eax,[0x1234]"). You'd also want at least 3 registers (instruction pointer, stack pointer and accumulator).

However; getting such a minimal computer to do anything useful will be a nightmare - it'd make more sense to make it slightly more powerful. Basically; you'd want to grab the "low hanging fruit" - include things (like a true copy/assignment operator or an OR operator) that are relatively easy to include but make it less painful (and faster).

Finally, redstone circuits are "awkward at best", and if you really don't feel like doing it to begin with then even the simplest possible ALU is likely to be more work than you're willing to undertake.


Cheers,

Brendan

XanClic wrote:Maybe this is helpful to you: http://en.wikipedia.org/wiki/One_instru ... t_computer.

What I've been taught in uni is that the von Neumann architecture is a “hardware minimal” implementation. If you don't know, such CPUs have one register only (besides the instruction pointer), being the accumulator. Every arithmetic instruction combines that accu and a value taken from an arbitrary memory location (which is given as an immediate operand). Of course, there are also load/store and branching instructions.

I guess the main problem with both of these designs is that they both require you to have a sufficient amount of memory, and I can imagine building that in Minecraft being probably the hardest part about it.

Sounds rather interesting. I'll certainly check it out.

m12 wrote:The simplest logic based computer, in my opinion, would be one which has one single bit register. For addition, NOT it. For subtraction, NOT it. for multiplication, AND the register with either 1 or 0, depending on the button pressed. For division, not sure.

A single bit computer? That an idea. Hadn't considered that.

Brendan wrote:Hi,

*snip*

This gives us an "even more minimal" list:

• subtract
  conditional branch

This list can't be reduced further; but it's only 2 operations, and it's all you need to do everything.

Of course you'd need to add addressing modes on top of this (minimum would probably be "register, immediate operand, value at address in register and value at immediate address" - e.g. "mov eax,eax", "mov eax,0x1234", "mov eax,[eax]" and "mov eax,[0x1234]"). You'd also want at least 3 registers (instruction pointer, stack pointer and accumulator).

However; getting such a minimal computer to do anything useful will be a nightmare - it'd make more sense to make it slightly more powerful. Basically; you'd want to grab the "low hanging fruit" - include things (like a true copy/assignment operator or an OR operator) that are relatively easy to include but make it less painful (and faster).

Finally, redstone circuits are "awkward at best", and if you really don't feel like doing it to begin with then even the simplest possible ALU is likely to be more work than you're willing to undertake.


Cheers,

Brendan

That's quite a novel you wrote there and I think I'll have to reread it a few times to consume it all. In any case thanks for the effort

Much of what you wrote I already knew. I have play around with redstone in minecraft quite a lot, just to pass the time, so I do know a few things. Actually it's an amazing learning tool.

But to get to the point, I did not know that you could do AND and OR with XOR and at this time I'm not quite sure how, though of course I'll read up on it. Doing it the other was around I easy though.

As for the difficulty of it... Well, it was really more the question that interest me, though I have played around with redstone quite a lot, made a couple working ALUs and such.

And yes, redstone is a *****, but again it's the limitations that makes it fun.


Once again, thanks a lot for the effort. Not that I expected anything less. You guys always pull through and I often have to restrain my self, not asking all my odd and pointless questions here.


Best regards.

Brendan wrote:e.g. "x = y" is the same as "x = x ^ 0; x = x ^ y"

That is the same as x ^ 0 ^ y, which is x ^ y NOT x = y.
Did you mean x ^ x ^ y?

Brendan wrote:you'll see that AND and OR can be done with XOR.

DeMorgan is all about replacing ORs with ANDs and vice versa, not XOR. Also, it is universally impossible: Consider a series of xors. Count the number of "1" bits. the number of "1" bits in the result is always the sum of bits in the inputs, minus an integer multiple of two - the case when two set bits counter each other. Therefore, if the number of 1 bits in all inputs together are even, then the number of "1" bits in the result must be even. if the number of bits is odd, the result must be odd.
1 | 1 has even set inputs and odd set outputs, which means that an implementation using xor must use an odd number of bits in other constants.
1 | 2 has even set inputs and even set outputs, which means that an implementation using xor must use an even number of bits in other constants.
The number of constant bits being "1" must be both even and odd.
This is a contradiction, therefore the assumption must be false.
Conclusion: OR can't be implemented using XOR. (and similar proofs can be made using any of AND/OR versus any of XOR/SUB/ADD)

"x = y" is the same as "x = x ^ 0; x = x ^ y"

Other than the obvious writing error (x = x ^ x; x = x ^ y), the proof assumes that registers are not aliased. This particular substitution is no longer capable of implementing jumps as a move would. While direct jumps can be written by precomputing the input operand, indirect jumps require conditionals for each possible target (yuck).

This gives us an "even more minimal" list:

Replace bit with value.
Jump if bit set.

Which allows all logic operations to be written as their truth tables, unconditional jumps by a write-one-jump-if and indirect jumps by having a conditional jump for each possible target.

You can replace all logic functions with either "nand" or "nor", as they are primitive logic functions.

Opcode wrote:You can replace all logic functions with either "nand" or "nor", as they are primitive logic functions.

The NOR way is actually the Minecraft way. You can make XOR and AND with 3 NOR, XNOR with 4, OR with 2, etc. Though often those NORs only acts as NOT gates.

@Combuster

I was rather going mad trying to figure out the XOR to AND/OR problem. Thanks a bunch for pointing out that it is i fact impossible.

Invert an odd number of inputs/outputs on a XOR and you got your self and XNOR and an even number (i.e. 2) will result in... well, XOR. How the heck that was supposed to result in AND/OR was confusing to say the least.

Hi,

Combuster wrote:

Brendan wrote:you'll see that AND and OR can be done with XOR.

DeMorgan is all about replacing ORs with ANDs and vice versa, not XOR. Also, it is universally impossible:

Doh - you're right

Opcode wrote:You can replace all logic functions with either "nand" or "nor", as they are primitive logic functions.

That's what I was trying to remember

m12 wrote:

Brendan wrote:e.g. "x = y" is the same as "x = x ^ 0; x = x ^ y"

That is the same as x ^ 0 ^ y, which is x ^ y NOT x = y.
Did you mean x ^ x ^ y?

Yes.


Cheers,

Brendan