Question on Turing Machine (equivalence)

Hello everyone.

I have a problem that I was unable to answer (nor any luck in finding
any help in all my immediately available materials). It was from some
old exam archive:

"Show that every recursively enumerable set is accepted by a Turing
Machine with only three non-accepting states and one accepting state."

The closest equivalent exercise I could find is from Hopcroft's
"Formal languages and their relation to automata" Chapter 6: "Show
that every TM is equivalent to a single-tape TM with one accepting and
two nonaccepting states."

But I do not have a solution to that either. Any help on how to start
proving this problem is greatly appreciated. Thanks.

.

Relevant Pages

  • Re: Why online poker is better for the money player.
    ... but I can tell you that my luck ... 12-year-old after playing for 2 weeks beating Nack Ballard. ... Poker players have as man or more "bad beat" ... >after accepting a bad double, or even worse, as in this case. ...
    (rec.games.backgammon)
  • Re: ruling please - self incrimination
    ... and it could be that the opponents know you for an honest opponent and ... for example in connection with revoke rulings. ... It is just luck. ... accepting a bad claim. ...
    (rec.games.bridge)
  • Re: how to install pics on PDA
    ... >> I've converted the files from jpeg to prc, and pbm with no luck. ... No luck on it accepting the file. ...
    (comp.os.linux.misc)