3 ms·

I don't remember the details, but I found this: http://en.wikipedia.org/wiki/Counter_machine#Two-counter_machines_are_Turing_equivalent_.28with_a_caveat.29 htt

by xyzzyz 15y ago

I don't remember the details, but I found this: http://en.wikipedia.org/wiki/Counter_machine#Two-counter_machines_are_Turing_equivalent_.28with_a_caveat.29 http://en.wikipedia.org/wiki/Counter_machine#Two-counter_mac... It seems that even 2 counters are enough for Turing machine. My class only came up with 3 counters for pushdown automaton, but I'm still happy with it, since we did it ourselves :)

alok-g 15y ago
Thanks. Helpful again. My understanding (after reading your first comment; would not have figured it out by myself!) was right (though incomplete still till I read the Wikipedia page).