User:Feuermonster/Ideas

A finite state machine with two register R and T which is connected to two other machines: M which calculates 1/3 + 1/9 + 1/27 + ... and P which generates a random bit 0-1 (entirely random). It has the instructions m which polls the (externally visible) state of M and saves it in R and p which polls a random bit from P and saves it in T. ? halts if T = 0 and ! halts if T != 0. X is xchg T,R. M returns 1 if it has reached 1/2 and 0 if it has not. There is a loop [...] which loops until R is not zero. Both T and R are initialized to 0.

Example programs

[m] loops until M has reached 1/2. M does not reach 1/2 in finite steps but does so (or maybe it does not) in infinite steps. The program can only terminate if it runs forever.

[p?] waits for the random machine to return 0.