News for hackers. Stuff that matters.
Re:Turing completeness bullshit by xyzzyz on Wednesday September 28, 2011 @04:11AM (#3046955)
Our model allowed us only to do INC, DEC and ZERO? on a counter, and it's easily seen that you cannot implement 2 counters using 1 counter with only ZERO?, INC and DEC, for instance by noting that you can recognize a^n b^n c^n language using automaton with two counters, you can (trivially) implement automaton with one counter using pushdown automaton, so if you were able to implement 2 counters using 1 counter, you could recognize a^n b^n c^n using pushdown automaton, which is easily seen to be impossible by applying pumping lemma for context free languages and usual characterization of pushdown automatons in terms of context free languages.

There are no comments on this comment yet.