An interesting next step to Turning machines I read about recently was Kolmogorov-Uspensky machines. They allow pointers and are nearer to real machines we use.

An interesting next step to Turning machines I read about recently was Kolmogorov-Uspensky machines. They allow pointers and are nearer to real machines we use. Whilst they still recognising the same languages in polynomial time as Turing machines, for some things they can compute and order of complexity class faster. Turing machines often end up traversing up and down the tape, linearising binary tree lookups for instance, whereas KU can do binary tree lookups in O(log(n)). Both machines do the lookups in P, but KU's particular P can be provably lower. [1] http://esolangs.org/wiki/Kolmogorov_machine http://esolangs.org/wiki/Kolmogorov_machine