Theory of Computation Flashcards
Name the three primary components of a Turing machine
Read/write head
Finite state machine
Infinite tape
What is the format of a transition function?
How is it represented in a state transition diagram?
δ(current state, read) = (new state, write, move)
Arrows between states, each with a condition
What is the importance of a Turing machine?
Anything a Turing machine can compute, a real-world computer can also compute, and vice versa. Therefore, Turing machines prove there are problems that can’t be solved by computers.
It is a general purpose machine.
Define ‘Universal Turing Machine’.
A Turing Machine that can simulate the behaviour of any other Turing Machine. It faithfully executes operations on the data precisely as the simulated Turing Machine would.
What is the name of the set of symbols that a Turing Machine can recognise?
Alphabet
Why are Universal Turing Machines said to act as interpreters?
They read their instructions in sequence before executing operations on their input data.
What type of object is enclosed in <angle> in Backus-Naur Form?</angle>
Non-terminal
What type of object cannot be broken down further in BNF?
Terminal
Why is BNF capable of representing some languages that cannot be represented by regular expressions?
It supports recursion
What is an intractable problem?
It cannot be solved in a reasonable amount of time for all but the smallest versions of the problem.
What is the typical time complexity of an intractable problem?
Exponential or worse
How might a programmer ‘solve’ an intractable problem?
Approximate a solution by taking a heuristic approach.
What type of problems have a polynomial (or better) time complexity?
Tractable
What is the significance of the Halting problem?
Shows there exists some problems that cannot be solved by a computer.
Describe the Halting problem.
It is possible in general to write an algorithm that, given any program and its inputs and without executing the program, can tell if it will halt.
