HACKER Q&A
📣 sagebird

Nice Enrichments of Turing Machines?


Turning equivalence makes me feel less inspired about computing ideas. I think I lack enough knowledge to know what is left that is interesting.

Are there good examples of machines which are technically Turing equivalent but bring certain unique phenomena into reach?

An example of me not really seeing fruitfulness:

Suppose I were to make a variant of a turning tape machine that could store irrational numbers instead of just ones or zeros.

Would it bring any interesting programs within reach that would be hard to express with 1’s and 0’s.

My guess is no- as to do anything with these irrational numbers you would probably do a series of comparisons, a binary search to, to find if a number is in a range, essentially sampling it into a binary number, and then acting on it.

Maybe there are further enrichments that would make this worthwhile? Like being able to instruct the tape to move by an irrational number instead of steps.

I am not trying to limit the discussion to my toy example.

So far the only model of computation I have come across that seems potentially different is quantum computing. Do others feel this is sufficiently different?


  👤 RGamma Accepted Answer ✓