Computability
Đã giới thiệu
Từ vựng
| English | Ý nghĩa |
|---|---|
| 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}
Luyện tập
The halting problem proof builds D(M) that —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
D flips the answer about itself - running D on D contradicts.
English
Diagonalisation, once
- 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}
Luyện tập
Rice's theorem covers —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Nontrivial properties of WHAT the program computes - undecidable.
English
The decidable cousin
- "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}
Luyện tập
DFA emptiness is decidable because —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
Finite graph, finite search: mark reachable states, check accept.