Counter machines with two or more counters are typically shown to be equivalent to Turing machines in courses on the theory of computation.  However, I have not seen a formal analysis of which languages can be recognized by a one-counter machine.  Are these languages equivalent to the context-free languages (perhaps by some clever construction relating them to PDAs), or are they an entirely different class of languages?
Which languages are recognized by one-counter machines?
computability;automata
A one counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). Languages recognized by one counter automata form a proper subset of the context free languages.For example a 1-counter automata can recognize the language $\{a^nb^n\}$ which is not regular, but cannot recognize the language $\{a^nb^ma^mb^n\}$ which is context free and can be recognized by a 2-counter automata, too.If k-DCA is a deterministic k-counter automata, and k-NCA is a nondeterministic k-counter automata, then we have the following proper inclusions:DFA (regular languages) $\subset$ 1-DCA  $\subset$  2-DCA 1-DCA $\subset$ 1-NCA If we don't allow $\epsilon$ transitions (switch to real time) then k-DCA $\subset$ k'-DCA for k < k'.Just for completion: there are languages that are context free but cannot be recgnized by counter automatas (k-DCA with k $\geq$ 2) (for example $\{ww^R\}$), and languages recognized by counter automatas that are not context free (for example $\{a^nb^nc^n\}$). A counter automata (in particular a two counter automata) can be Turing complete only if its input and output are properly encoded (see Wikipedia entry for details).