# Post Machine

• Nov 6th 2010, 03:43 PM
Apprentice123
Post Machine
It is possible to build a Post machine that recognizes the language:
${a^{n+1} b^n | n >= 0 }$
??
• Nov 7th 2010, 11:44 AM
emakarov
I used to have a brochure "Post Machines", but I never learned the difference between Post and Turing machines. However, according to Wikipedia, they are equivalent. Since the language you've given is Turing-decidable (more precisely, context-free), the answer to your question is yes.

Edit: This probably feels like an insult if you were actually asking for help in constructing the machine... See joke #19 here.
• Nov 8th 2010, 02:53 PM
Apprentice123
Quote:

Originally Posted by emakarov
I used to have a brochure "Post Machines", but I never learned the difference between Post and Turing machines. However, according to Wikipedia, they are equivalent. Since the language you've given is Turing-decidable (more precisely, context-free), the answer to your question is yes.

Edit: This probably feels like an insult if you were actually asking for help in constructing the machine... See joke #19 here.

I do not see how to build a Post machine for this language, if the Post machine only works with:
begin, accepts, rejects, X<-read(X) and X<-Xa