Computability

Vocabulaire

English	Sens
Turing machine	Turing machine
halting problem	halting problem
diagonalisation/daɪˌæɡənəlaɪˈzeɪʃn/	diagonalisation

English

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}

Pratique

The halting problem proof builds D(M) that —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

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}

Pratique

Rice's theorem covers —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

"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}

Pratique

DFA emptiness is decidable because —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui