Computability

Vocabulary

English	Meaning
Turing machine	An abstract computing machine with finite control and a read-write tape.
halting problem	The undecidable problem of determining for every program and input whether execution eventually stops.
diagonalisation/daɪˌæɡənəlaɪˈzeɪʃn/	A construction differing from each member of a proposed list at a selected position.

The formal algorithm

The Turing machine: tape, head, states — the formalisation of "algorithm". The halting problem: does $M$ halt on $w$? Suppose a decider $H$ exists; build $D(M)$ = run $H(M,M)$, and if it says "halts", loop forever. Run $D$ on $D$: contradiction.

{exercise:uni-cs1103-tm}

Practice

The halting problem proof builds D(M) that —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

Enumerate all machines and inputs; diagonalisation builds $D$ to disagree with the diagonal entry of every row — so $D$ differs from every machine, yet is one. The same shape proves the reals uncountable and Rice's theorem.
Rice: every nontrivial semantic property of programs is undecidable — "does $P$ ever print banana?" reduces halting to printing (the suite runs the wrapper).

{exercise:uni-cs1103-rice}

Practice

Rice's theorem covers —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

"Does DFA $D$ accept the empty language?" is decidable: mark reachable states from $q_0$ (finite graph search); accept iff no accepting state is marked. Finiteness makes it searchable — the halting problem's infinite tape is exactly what breaks the argument.

{exercise:uni-cs1103-decidable}

Practice

DFA emptiness is decidable because —

Difficulty 1/5 · 100 coins + a small bonus on first completion today