This paper surveys small universal Turing machines. What are some examples of small universal monotone Turing machines, as described by Schmidhuber? Which of these are efficient (polynomial time) simulators of Turing machines?
Monotone machines are Turing machines with a one-way read-only input tape, some work tapes, and a one-way write-only output tape. The input tape contains a one-way infinite sequence of 0's and 1's and initially the input head scans the leftmost bit. The output tape is written one symbol at a time, and the output is defined as the finite binary sequence on the output tape if the machine halts, and the possibly infinite sequence appearing on the output tape in a never-ending process if the machine does not halt at all.
From page 276 of An introduction to Kolmogorov complexity and its applications by Li and Vitanyi.
