Labs

Lab 8.3: Incompleteness and Ambiguity

ITM Help

As you can imagine, the cryptic nature of how we describe TMs make it easy to define one incorrectly. It is one thing if a set of rules doesn't produce the desired result. In such a case, ITM will follow the rules to an incorrect conclusion. There are, though, ways to define a TM so that it confuses our simulator or terminates the simulation. Let's examine three of them here. For each exercise, write down the TM that you define, run it in ITM, and answer the question posed. Your machines need not address any "real" problem other than that of illustrating the situation described.

For these exercises you won't be importing any data - you have to set the tape and the rules on your own. To set the tape, enter any string directly into the Input Tape field and click Set Tape.

To enter rules, double click on a row (starting with the one labeled 1:) and enter values for the input state, input symbol, output state, output symbol, and the move (L or R). Then click OK to record the rule in the rule list.

  1. Define a TM that demonstrates what happens when ITM runs a TM that contains ambiguous rules (that is, more than one rule for a given input symbol-state pair).

  2. Define a TM that demonstrates what happens when ITM runs a TM that directs it to move off the left edge of the tape.

  3. Define a TM that demonstrates what happens when ITM runs a TM with an incomplete rule base (for example, the rules of the TM direct the simulator to a particular state, and there are no rules describing what it should do in that state).

Labs

MODULES:



© 2004 Thomson/Brooks Cole, All Rights Reserved.