Turing Machines and Undecidability

mathematical model of computation

Turing Machines

Turing machines are primarily a mathematical construction. A Turing machine (TM) consists of:A finite set of states: initial state(when the TM starts, it is in this state) and accepting states(if the TM ends in one of these states, it says yes); Transition rules that determine what to do based on current state and content of memory tape at current position; An alphabet, the set of symbols that can be stored on the memory tape.

The Church-Turing Hypothesis

Anything which can be computed by any automatic method, can also be computed by a Turing machine.

If a model can also do everything that a Turing machine can, then it is called a Turing-complete model of computation.

The RAM Model

Models the way modern computers operate, with registers and memory cells that can be immediately accessed.

Comparison-Based Sorting

We will prove that any such algorithm must make Ω(n log n)
comparisons (and thus take Ω(n log n) time)

Undecidability

decision problems

The answer is just a single bit of information,“yes” or “no”.A decision problem is decidable if there exists an algorithm for solving the problem without any efficiency considerations.

The Halting Problem

Turing machine M, and input x to M. Does M halt when run on the input x?
The Halting Problem is undecidable.

Halting On Empty Input

It is undecidable.

Halting on All Inputs

It is undecidable.

Recursively Enumerable Problems

There exists an “algorithm” which terminates whenever the answer is
“yes” but does not terminate on “no” instances.Problems which have algorithms like this are called recursively enumerable.

Turing reduction

A Turing reduction (also called Cook reduction) from a problem
X to a problem Y is an efficient algorithm for problem X which is
allowed to assume an algorithm for Y as a black box.

Vertex Cover

Independent Set

Set Cover

3-Sat

Karp Reductions

X ≤p Y if given any instance A of problem X, we can in
polynomial time construct an instance f (A) of problem Y such that
the answer to A is the same as the answer to f (A).

Turing reduction is a type of reduction that is stronger than Karp reduction. A problem A is Turing-reducible to problem B if there exists a Turing machine that can solve problem A by making a polynomial number of calls to a black-box subroutine for problem B. In other words, if we can use an algorithm for problem B to solve problem A, then A is Turing-reducible to B. Turing reduction preserves the complexity class of a problem, meaning that if A is Turing-reducible to B and B is in a certain complexity class, then A is also in that complexity class.

Karp reduction, also known as polynomial-time reduction, is a weaker form of reduction than Turing reduction. A problem A is Karp-reducible to problem B if there exists a polynomial-time algorithm that can transform any instance of problem A into an instance of problem B such that the answer to the transformed instance is the same as the answer to the original instance of problem A. In other words, if we can use an algorithm for problem B to solve a transformed version of problem A in polynomial time, then A is Karp-reducible to B. Karp reduction preserves the complexity class up to polynomial factors, meaning that if A is Karp-reducible to B and B is in a certain complexity class, then A is also in that complexity class up to polynomial factors.

Good reference

https://www.cs.rochester.edu/u/nelson/courses/csc_173/computability/undecidable.html
http://www2.lawrence.edu/fast/GREGGJ/CMSC515/chapt05/Reducibility.html
https://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures.php