Turing Machine theory Flashcards
Name the components of a Turing Machine
- A set of transition rules
- A sensing read-write head that can read AND write from an INFINITELY LONG tape.
- A start state
- Set of accepting states
Why can a UTM be considered to be more powerful than any real computer?
A UTM has an infinite amount of memory / tape
What is a Universal Turing Machine? (UTM)
A Turing machine that can execute the behaviour of any other Turing machine.
Instructions for a Turing machine are stored on the UTM’s tape.
What is the Halting problem?
Non-computable, unsolvable problem of writing a program that can tell whether a given program will halt - without running the given program.
What is an intractable problem?
A problem that can be solved, but has an exponential (or worse) time complexity.
What approaches can a programmer take to “solve” an intractable problem?
Using an algorithm that estimates based on experience which provides a close-to-optimal solution.
They could use a heuristic method, e.g. trial and error.
What are heuristics?
(Potential) non-optimal approaches that use experiences to make informed guesses to assist in finding a solution to an intractable problem.
What is the relationship between a Turing machine and an algorithm?
If, and only if, an algorithm exists to solve a problem, then a Turing machine can be designed to solve the problem.
