Computing Theory time

posted Mar 16, 2003

Please ignore if you're not into computing theory.

Says Den Beste:

My original statement was that a single Turing machine cannot perfectly simulate a system which consists of two Turing machines such that the ratio of the clock rates for those two Turing machines is a transcendental number.... [attempted proof clipped] ... Am I right? ... Can my proposed idea be restated in a way which truly does make it uncomputable?

No, that doesn't work; the simulation machine doesn't need to do the full calculation of the ratio. It only needs to do enough to compute the next step, then it can abandon the ratio calculation for this iteration. Eventually no more computation will be necessary, as the machine finds the most significant digit where the ratio diverges and that's all it needs; the rest is garbage. The amount of work required is certainly bounded only by infinity and nothing tighter ("limit" isn't really appropriate here, "bounded" is), but it will never reach that under your formulation.

If the original machines finished in finite time, so will this one.

An interesting case is when the two numbers do eventually cause the original machines to execute precisely simultaneously. (This is when the computation does go to infinity.) Detecting that one transcendental number divided by another is a rational number is impossible, because it takes forever, but that's a known fact. I would inclined to call that a malformed input, rather then anything special, because there is some other input (the rational ratio of the two numbers) that performs identically but doesn't hang the machine. Lots of computer science stuff breaks when presented with transcendental numbers; what's surprising is not that this doesn't work, but that the case where the ratio is transcendental does.

As for question four, answering that would involve creating a mechanism of computing that would then be more powerful then Turing Machines (able to compute a problem the TMs couldn't), and that runs you into the Church/Turing hypothesis. Of course that's no proof, but it does mean it's unlikely this is going to work. ;-)