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 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
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}
ฝึกฝน
Rice's theorem covers —
ความยาก 1/5 · 100 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
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}
ฝึกฝน
DFA emptiness is decidable because —
ความยาก 1/5 · 100 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
Finite graph, finite search: mark reachable states, check accept.