Theory of computation flashcards

Topic 4: Theory of computation

What is a finite state machine (FSM)?

A model of computation with a finite set of states, a start state, inputs and transitions between states. An FSM with no output can accept or reject input strings.

What is a Mealy machine?

A finite state machine with outputs, where each output is determined by the current state and the input (shown on the transitions).

What is a regular expression? What do *, + and ? mean?

A way of describing a set of strings (a regular language). * : zero or more of the previous item. + : one or more. ? : zero or one. | separates alternatives.

What is a Turing machine?

A theoretical model of computation: a finite state machine with a read/write head on an infinitely long tape divided into cells, moving one cell left or right per step according to its transition rules.

What is a universal Turing machine?

A Turing machine that can simulate any other Turing machine by reading that machine’s description and its input from the tape: the idea behind the stored-program computer.

What is the Halting problem?

The problem of deciding, for any program and input, whether the program will eventually stop. It has been proved that no algorithm can solve it: some problems are not computable.

What is the difference between tractable and intractable problems?

Tractable: can be solved in polynomial time or better. Intractable: solvable in theory, but no polynomial-time algorithm is known, so heuristic methods are used for large inputs.

Why is Backus–Naur Form (BNF) needed as well as regular expressions?

Some languages, such as those with nested structures, cannot be described by regular expressions. BNF can define them, including recursive rules, so it is used to define programming language syntax.

What is the order of complexity of an algorithm that halves the problem each step?

Logarithmic, O(log n), as in binary search. Constant O(1) < logarithmic < linear O(n) < polynomial O(n²) < exponential O(2ⁿ).