Thursday, May 28, 2009

F*ctor - a 0-dimensional Turing tarpit.

Following a post of one of my friends to the http://manage.yore.ma/eso/, I felt a bit inspired,
so I wanted to write up something fun. So, here's the experiment - an imaginary language which holds the entire program and data memory in a single variable!

The F*ctor machine has only other elements are a single instruction, and a single variable which holds the Program, and Data, and the machine state, in just a single natural number X. The "single instruction", however, is a bit difficult to describe, so I will attempt to describe it in terms of smaller "micro-operations" - they do not really change nor are visible to the user, they are here mostly for the sake of explanation. The temp variable in the pseudocode is just for the sake of ease of comprehension.

The machine can really efficiently calculate Prime(N) (being the Nth prime, that is Prime(0) == 2; Prime(1) == 3, Prime(2) == 5, etc.)

Also it can count how many times is the given number divisible by some prime: CountPrime(V, P); CountPrime(2,2) == 1, CountPrime(9,3) == 2; CountPrime(13,3) == 0.

Finally, the third operation is the destructive divide: DivideBy(V, P) - try to integer-divide V in-place by a prime P ith no remainder, and return True if we were successful, and False if no remainder-free division is possible.

The remaining operations that comprise the single cycle are some trivial arithmetics.

the single cycle of execution:


one_cycle(X) {
local CurrentP = CountPrime(X, 3);
while(DivideBy(&X, 2)) {
if(not DivideBy(&X, Prime(CountPrime(X, Prime(CurrentP))))) {
return X * 3 * 3;
}
}
return X * 2^CountPrime(X, Prime(CurrentP)) * 3;
}


So running the program consists of repeatedly executed "X = one_cycle(X)".

If we take a closer look, then this is nothing more than a folded version of Reverse-subtract and skip if borrow single-instruction machine, with "memory contents" at location N being the number of times the X is divisible by Nth prime number. As it is visible, the accumulator is memory-mapped at 0 (see these divisions/multiplications by 2?) and the program counter is memory-mapped at 1 (see the multiplications either by 3 or by 9 ?)

So, unless I made a bug somewhere in the logic, we have a Turing-complete absract machine squashed into a single variable.

No comments: