Computability

מילון מונחים

English	משמעות
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.

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}

אימונים

The halting problem proof builds D(M) that —

רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום

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}

אימונים

Rice's theorem covers —

רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום

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}

אימונים

DFA emptiness is decidable because —

רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום