2003-03-07

The Universe is a two’s complement machine

What follows is a transcription of Item 154 (by R.W. "Bill" Gosper) of HAKMEM, a 1972 memo from the MIT Artificial Intelligence Laboratory.

HAKMEM is full of interesting tidbits (some others are pointed out in The Jaron File).

The myth that any given programming language is machine independent is easily exploded by computing the sum of powers of 2.

  • If the result loops with period = 1 with sign +, you are on a sign-magnitude machine.
  • If the result loops with period = 1 at -1, you are on a twos-complement machine.
  • If the result loops with period > 1, including the beginning, you are on a ones-complement machine.
  • If the result loops with period > 1, not including the beginning, your machine isn't binary -- the pattern should tell you the base.
  • If you run out of memory, you are on a string or Bignum system.
  • If arithmetic overflow is a fatal error, some fascist pig with a read-only mind is trying to enforce machine independence. But the very ability to trap overflow is machine dependent.

By this strategy, consider the universe, or, more precisely, algebra:

let X = the sum of many powers of two = ...111111

now add X to itself; X + X = ...111110

thus, 2X = X - 1 so X = -1

therefore algebra is run on a machine (the universe) which is twos-complement.

No comments: