TODO watch https://www.youtube.com/watch?v=26zcLaUreok https://www.youtube.com/watch?v=ASgv7SmUCzo https://www.youtube.com/watch?v=iN0auyB0Hv0&list=PLylTVsqZiRXOFmaByWXrpSWQIWLE4X_4g&index=3 https://www.youtube.com/playlist?list=PLylTVsqZiRXOFmaByWXrpSWQIWLE4X_4g

Undecidable Problems

Proof: Halting Problem is Undecidable

Write an algorithm $H$ such that given:

• the description of an algorithm $A$ (which requires one input)
• an input $I$

Then $H$ will return $1$ if $A$ stops with input $I$ and $0$ if it does not.

Assume $H$ exists, we can then write an algorithm $H^{\prime }$ such that $H^{\prime }$ takes an input an algorithm $A$ and computes $H(A,A)$. If the result is $0$ then $H^{\prime }$ answers $1$ and stops, otherwise it loops forever.

Since $A$ is arbitrary, it could be $H^{\prime }$ itself. We obtain a contradiction $H^{\prime }(H^{\prime })$ stops if and only if $H^{\prime }(H^{\prime })$ does not stop. So $H$ cannot exist.

Visual example of Halting Problem undecidability

Let’s assume $G$ is a program that takes a Go state and outputs the optimal move: The program sometimes gets stuck and will never return an output.

Let’s say $H$ is a program that takes $G$ and a Go state as inputs and outputs true iff $G$ will halt on that Go state (false otherwise).

procedure H(P, I):
	if P(I) halts:
		return True
	else:
		return False
end procedure

Let’s make some modifications to $H$ to produce $H^{\prime }$:

procedure H'(P):
	if P(P) halts:
		loop forever
	else:
		halt
end procedure

$H^{\prime }$ will take a program $P$ as input:

• if $P(P)$ halts then $H^{\prime }$ will run forever
• if $P(P)$ runs forever then $H^{\prime }$ will halt

Now we try to feed $H^{\prime }$ into itself:

We reach a contradiction:

• If $H^{\prime }(H^{\prime })$ halts then it runs forever
• If $H^{\prime }(H^{\prime })$ runs forever then it halts

By assuming that a program that solves the halting problem exists we have found a contradiction. Therefore, it’s not possible for such a program to exist.

Decidable Problem

A problem is said to be decidable if it is possible to design a program to answer the problem within a finite time.

Link to original

We say the halting problem is undecidable. It demonstrates a theoretical limit to computability.

Partial Functions and Computability

Algorithm (Computability)

An algorithm has three characteristics:

• Has a finite description of a computation in terms of elementary instructions
• Is a deterministic procedure: next step is uniquely defined
• Always produces a result no matter the input (i.e. halts)

Link to original

To allow us to represent unending computations (that do not always return a result), and to ignore certain unnecessary details, we consider programs to be partial functions.

Examples of these sorts of expressions include:

• true + 3: not well defined (type error) addition is a total function on natural numbers
• 10/0: not defined division is a partial function on natural numbers
• expression fact(-1) does not have a value for: fact(x) = if x = 0 then 1 else x * fact(x - 1) fact defines a partial function on integers

Cartesian product of sets

The Cartesian product of sets $A$ and $B$ is the set $$ A \times B = \{ (x, y) | x \in A \text{ and } y \in B \} $$

$A\times B$ consists of ordered pairs $(x,y)$ where $x\in A$ and $y\in B$.

For example, let $A=\{1,2\}$ and $B=\{a,b,c\}$. Hence, $A\times B=\{(1,a),(2,a),(1,b),(2,b),(1,c),(2,c)\}$.

Generic Format

The Cartesian product of sets $A_1,A_2,...,A_k$ is the set $$ A_1 \times A_2 \times ... \times A_k = \{ (x_1, x_2, ..., x_k) | x_i \in A \text{ for } i = 1, 2, ..., k \} $$

$A_1\times A_2\times ...\times A_k$ consists of those $k\text{-tuples }(x_1,x_2,...,x_k)$ where $x_1\in A_1,x_2\in A_2,..$

Link to original

Set member

Membership of a set is denoted with $\in$, e.g. $b\in \{a,b\},c\notin \{a,b\},(a,1)\in \{a,b\}\times \{1,2\}$.

Link to original

Function notation

$f:A\to B$ indicates that the function $f$ takes an input from the set $A$ (domain) and produces an output in the set $B$ (image / codomain).

Link to original

Partial function

A partial function $f:A\to B$ is a subset of $A\times B$ such that if $(x,y)\in f$ and $(x,z)\in f$ then $y=z$. i.e. for each element of $A$, there is at most one result in $B$.

Link to original

Total function

A total function $f:A\to B$ is a function where for every element $A$, there exists an output $B$

Link to original

Computer programs define partial functions.

The class of functions on the natural numbers that can (in an ideal world where time and space are unlimited) be computed by a program is called partial recursive functions or computable functions.

Computable function

A function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ on words from ${\Sigma }^{\ast }$ is computable if there is a deterministic Turing Machine $M_f$ s.t.: (or there is a lambda-term)

• $M_f$ accepts all input words $w\in {\Sigma }^{\ast }$
• when started in configuration $(q_{\text{init}},ϵ,w)$, the machine eventually terminates in configuration $(q_{\text{accept}},ϵ,f(w))$.

The machine transforms the contents of the tape from $w$ to $f(w)$ and returns the tape head to the start of the word.

Link to original

Turing-complete

A programming language is Turing-complete if any computable function can be written in this language.

Link to original

Abstract Models of Computation

We need a computational model to abstract away from material details of a programming language and processor we may be using.

Most well known are:

• Turing Machines
• The Lambda-Calculus

Church’s Thesis says that the same class of functions on the integers can be computed in any sequential model of computation. This proves that the Lambda-calculus and Turing machines compute exactly the same class of functions.