Chapter 12: Theory of Computation

Question 1

Functions

Answer 1

• Function: each possible input value maps to a single output value
• Computable functions: can be computed by some algorithm
• Non-computable function: can not be computed by any algorithm

Question 2

Turing machines

Answer 2

• Turing machines: tool for studying the power of computing (algorithm processing)
• Turing machine components:
  Control unit (state and actions)
  Tape (infinite)
  Read-write head

Question 3

Church-Turing thesis

Answer 3

• Turing computable functions are equivalent to computable functions

Question 4

The halting problem

Answer 4

• A program is self-terminating if its execution terminates when started with itself as input.
• The halting problem:
  Given the encoded version of any program, return 1 if the program is self-terminating, or 0 if it is not.

Question 5

Polynomial and non-polynomial problems

Answer 5

Polynomial problem: problem for which there exists an algorithmic solution with complexity class O(n^x) for som x

• Non-polynomial problem: problem for which there exists no algorithmic solution within complexity class O(n^x) for any x
• Polynomial problems are practically solvable (and theoretically solvable), while non-polynomial problems are practically unsolvable (but theoretically solvable)
• Exponential growth O(2^n)) is non.-polynomial

Question 6

Non-deterministic polynomial problems

Answer 6

• Non-deterministic algorithm: “algorithm” whose steps may not be uniquely and completely determined by the process state.
• Non-deterministic polynomial problem: problem for which there exists a non-deterministic algorithmic solution within complexity class O(n^x) for som x
• Example:
  traveling salesman problem: find the best way to visit a number of cities.

Question 7

P versus NP

Answer 7

• P: the class of polynomial problems
• NP: the class of non-deterministic polynomial problems
• Whether NP is bigger than P is currently not known