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.

Saturday, May 16, 2009

A "nod" X11 linux interface

Today I wanted to spend the evening doing something different and fun, and came up with an idea to play around with some of the opencv's functions. Well, did not play that much - just slightly tweaked the facedetect.c, to get what I called a "nod interface".

When you compile and launch the program, it pops up the screen with the video. If all goes well and you are sitting in front of your camera, you should see a circle around your face. If you do not see it - move closer and/or get a smoother background.

The few lines of pretty silly code that I've added does the following: calculates the two averages of the last N points of the center of the detected face object - "fast" (N=4) and "smooth" (N=8).

If you don't move your head the delta between these will be almost 0 - it gets forced down to zero by a simple check against the threshold.

If you nod - then obviously the "fast" average moves down faster than the "smooth" one - so if you nod energetic enough, the computer will notice it and will send a few "arrow down" synthetic events via the XTest X11 extension. If you manage to "nod up" (unnatural, but somewhat doable) - then it will send the equivalent number of "arrow up" events.

The counter-movement (returning the head back after the nod) is compensated by another simple logic - it's needed to have at least 4 "zero-delta" cycles in order to let the detected delta through.

The end result is that with some amount of luck you might manage to read things from your laptop hands-free. Should be good for reading the /. threads :-)

this file is the tweaked facedetect.c - the long line to feed to the compiler is in the comments in the beginning.

Depending on the speed of your computer, you might need to adjust some of the thresholds.

Enjoy!

Thursday, May 7, 2009

Hercules DJ Console RMX linux midi drivers

Yay! Open source and all. Get the MIDI out of the RMX.

Grab them here

Saturday, May 2, 2009

A very compact renderer

Been a while since I babbled something here.

So to ensure I'm still alive and kicking - here's something neat: a renderer in under 600 lines of code.

Minilight has a bunch of implementations in various languages.

A very nice toy.