Results 1 to 3 of 3

Math Help - Post Machine

  1. #1
    Super Member
    Joined
    Jun 2008
    Posts
    829

    Post Machine

    It is possible to build a Post machine that recognizes the language:
    {a^{n+1} b^n | n >= 0 }
    ??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Quote Originally Posted by emakarov View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Turing Machine
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2010, 07:39 AM
  2. Turing machine
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: August 21st 2010, 08:17 AM
  3. Atwood Machine
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: September 18th 2009, 04:22 PM
  4. atwood machine
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: February 7th 2009, 11:49 AM

Search Tags


/mathhelpforum @mathhelpforum