# 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

ais a member of the domain andba 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 L_{odd} would look like:

*L*_{odd} = {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

- A finite set of
*k*states*Q*= {q_{1}, ..., q_{k}} - A finite set of
*n*symbols*S*= {s_{1}, ..., s_{n}} - 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 problemif there is a DTM such that for allxoff'sdomain and iff(x) = ythen DTMMhalts on inputx, after a finite number of steps, with outputy.

## 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

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

*dpn*. If

_{i}*dpn*gives for the natural number 2 back a 0,

_{i}*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.

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 10^{3} natural numbers, the machines with 2 states map to 19^{6} 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 ** tmDpn_{HALT}**, no Turing Machine that can compute whether an algorithm will halt on a specific input.

*dpn_{halt} (i) = 1 if given input i, tmDpm_{i}(i) = 0, or tmDpm_{i}(i) = *, 0 otherwise*

with i ∈ ℕ.

## Proof

Assume there is an uncomputable problem ** dpn_{UC}**. We try to show that if it is computable

**would also be computable. (Again: Proof by Contradiction, see Epimenides, 600 BC)**

*tmDpn*_{HALT}**Definition of dpn_{UC}**

*dpn*co-domain is 1 if input i,

_{UC}*tmDpn*(i) = 0 or

_{i}*dpn*= * (where * is the undesirable behaviour), otherwise the output i 0.

_{i}**Definition of tmDpn_{UC}**

*tmDpn*returns 1 only and only if

_{UC}*tmDpn*does not return 1.

_{i}Suppose *tmDpn _{UC}* does indeed exist, then it must be the k-th member on the list of Turing Machines for DPN.

*tmDpn _{k}* =

*tmDpn*

_{UC}According to the definition of *tmDpn _{UC}* this machine should return 1 if and only if

*tmDpn*does not return 1 for input

_{k}*k*. This is impossible, since

*tmDpn*=

_{k}*tmDpn*.

_{UC}In conclusion *tmDpn _{UC}* =

*tmDpn*does not exist and

_{UC}*tmDpn*does not exist. ■

_{HALT}## References

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