CSC4170: October 27 Quiz

What does it mean if a Turing machine is a decider?

A Turning machine is a decider if it is guaranteed to halt on every possible input, meaning it always finishes running and reaches either an accept state or a reject state without ever falling into an infinite loop.

What does it mean if a Turing machine recognizes a language over an alphabet?

A Turing machine recognizes a language over an alphabet if and only if the machine accepts every string that belongs to the language, and does not accept any string that is not in the language.

What does it mean if a Turing machine decides a language over an alphabet?

A Turing machine decides a language over an alphabet if and only if the machine accepts every string that belongs to the language, and rejects any string that is not in the language.

What is the proof idea of Theorem 3.13?

Every multi-tape Turing machine has an equivalent single-tape Turing machine. In other words:

1. The contents of each tape is stored in separate sections of one tape

2. Special symbols are used to indicate each tape’s head position

3. The single-tape machine scans the tape to find the head positions, read the symbols, and update to simulate one step of the multi-tape machine

4. The process continues until the simulated machine accepts or rejects.

What is the proof idea of Theorem 3.16?

Every non-deterministic Turing machine has an equivalent deterministic Turing machine. In other words:

1. A non-deterministic machine can make multiple choices at each step.

2. A deterministic machine systematically explores all these choices in a breadth-first search.

3. If any path reaches an accepting state, the deterministic machine accepts.

4. If no paths accept, it rejects.