Thread: Post Machine

It is possible to build a Post machine that recognizes the language:

??

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.

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