Decidability of Computational Problems

A famous decision problem is Alan Turing's halting problem. But first we have to understand how a computational problem can be defined as mathematical function.

Computational problems

Consider the following specification of a computational problem:

Name: Sum
Inputs: Two integers a and b
Outputs: An integer s
Precondition: None
Postcondition: s ≥ a and s ≥ b

Now to define this problem as mathematical function, we must understand that a function is

"a subset of the Cartesian product of two sets (the domain and co-domain), where a is a member of the domain and b a member of the co-domain".

(Piwek et al, 2013)

Thus we can formulate the computational problem of a sum as:

$$ sum: \mathbb{N} \times \mathbb{N} {\longrightarrow} \mathbb{N}$$

And as a concrete example we could write: sum((2, 4)) = 6.

Decision problems

The decision problem whether a natural number is even, can be described as

$$ f: \mathbb{A} {\longrightarrow} { 1, 2 } $$

where A is the set ℕ of natural numbers. In case we want to decide whether a natural number is odd we write:

odd: ℕ ⟶ {0, 1}.

An enumeration of the Language of odd Lodd would look like:

Lodd = {1, 3, 5, 7, 9, ...}

Turing Machine

Now we can express a Touring Machine using set notation:

A Turing Machine Mis a tripe, (Q, S, I) consisting of

  1. A finite set of k states Q = {q1, ..., qk}
  2. A finite set of n symbols S = {s1, ..., sn}
  3. A finite set of instructions I. Each instruction is a tuple (c, A) consisting of:
    • A condition c ∈ Q ⨯ (S ∪ {blank})
    • A triple of actions A ∈ {Write x : x ∈ (S ⨯ {blank})} ⨯ {NextState q: q ∈ Q} ⨯ {MoveLeft, MoveRight, MoveStay}

For each condition there is at most one instruction, such that (c, A) ∈ I and (c, A') ∈ I then A = A'. Therefore a touring machine as it is defined here is a deterministic touring machine, or DTM.

Using this formal notation we could describe an instruction i to add sequences of ■ as:

((0, ■), (Write ■, NextState 0, MoveRight))

If we reach a cell on the tape of the machine that has no such instruction i for its state k and symbol n, the machine halts.

The Church-Turing thesis by Alonzo Church states that every algorithm can be described with a deterministic touring machine.

An example for a program that never halts would be:

x = 5
while x > 0:
  x -= 1
  if x == 2:
    x = 5

Is it possible to automatically detect whether an algorithm ever halts? The answer is no, there exist no algorithm and there is proof for this problem, known as the Halting Problem. First, let's formulate a computational problem rigorously:

A computational problem is a computable problem if there is a DTM such that for all x of f's domain and if f(x) = y then DTM M halts on input x, after a finite number of steps, with output y.

Non-Computable Problems

It can be proven that there are uncomputable computational problems, e.g. there are decision problems with domain ℕ that are non-computable. To proof that we have to proof the following theorem:

Theorem

The set of decision problems with domain ℕ, DPN is uncountable and the set of Turing Machines TM(DPN) that solves instances of DPN is countable.

From this two assumptions it follows that there are DPN for which are no TM(DPN), read: there are DPN for which there are no algorithms. We try to proove both theorems.

Proof

1)

We try to put all problems in DPN into a 1 to 1 relationship with the natural numbers to show it is countable. (Proof by contradiction: we want to show that this is not possible)

Enumerating DPN: dpn1, dpn2, dpn3, ...

Each dpn is a decision problem that is a function of a natural number to either 0 or 1. (Whether the natural number lies in dpn's domain or not).

It is easy to construct a dpn- that is the inverse of a dpni. If dpni gives for the natural number 2 back a 0, dpn- would give back a 1. In conclusion dpn- cannot be in the list of dpn1, dpn2, dpn3, ... because it differs from each dpn in DPN in at least one value. To avoid contradiction we have to give up the idea that DPN is countable.

2)

All Touring machines have a finite number of states q and a finite number of symbols s. The resulting number of triples of instructions for all states and symbols of a single touring machine is n x (m + 1). 1 for when the tape is emtpy. Each cell in turn can have 9k + 1 different contents. Given that the set of symbols S = {0, 1} there are k states, resulting in (9k + 1)3k possible machines. This means a one-to-one correspondence to natural numbers can be set up. The first machines with one state map to the first 103 natural numbers, the machines with 2 states map to 196 natural numbers, and so forth. Thus the numbers of TM(DPM) are finite and therefore countable.

It follow that DPN is uncountable and TM(DPN) is countable and therefore |DPN| > |TM(DPN)| and not all computational problems are computabe. ■

Let's summarise:

  • Undecidable problem = non-computable
  • Decidable problem = computable
  • Algorithm that solves decision problem after a finite number of steps = effective procedure
  • Turing Complete = Algorithm that can simulate any other algorithm. (e.g. Python or the Universal Turing machine)

Halting Problem

The halting problem says that there is no algorithm that can verify whether another algorithm halts on specific input or not.

Please note that halting on specific input is desirable from an algorithm, but that if the machine or algorithm never halts, loops or does not give valid output, it is undesirable behaviour.

Theorem

We want to show there is no tmDpnHALT, no Turing Machine that can compute whether an algorithm will halt on a specific input.

dpnhalt (i) = 1 if given input i, tmDpmi(i) = 0, or tmDpmi(i) = *, 0 otherwise

with i ∈ ℕ.

Proof

Assume there is an uncomputable problem dpnUC. We try to show that if it is computable tmDpnHALT would also be computable. (Again: Proof by Contradiction, see Epimenides, 600 BC)

Definition of dpnUC
dpnUC co-domain is 1 if input i, tmDpni(i) = 0 or dpni = * (where * is the undesirable behaviour), otherwise the output i 0.

Definition of tmDpnUC
tmDpnUC returns 1 only and only if tmDpni does not return 1.

Suppose tmDpnUC does indeed exist, then it must be the k-th member on the list of Turing Machines for DPN.

tmDpnk = tmDpnUC

According to the definition of tmDpnUC this machine should return 1 if and only if tmDpnk does not return 1 for input k. This is impossible, since tmDpnk = tmDpnUC.

In conclusion tmDpnUC = tmDpnUC does not exist and tmDpnHALT does not exist. ■

References

Piwek, P., Walker R., Willis A. (2013) Algorithms, data structures and computability: Computability, Milton Keynes, The Open University.