Тьюрінг Машина: Проста Модель Всіх Обчислень

Binary Search Algorithm

Alan Turing's 1936 paper described the simplest possible model of a calculating machine, and it turned out to be powerful enough to define what "computable" even means. A Turing machine has an infinite tape divided into cells, each holding a symbol from a finite alphabet; a head that reads and writes one cell at a time and can move left or right; a finite set of internal states; and a transition table that says, for each (state, symbol) pair, which symbol to write, which way to move, and which state to enter next.

transition rule:  (state, read) → (write, move, next_state)

example — binary increment, rightmost bit first:
(scan, 0) → (0, RIGHT, scan)
(scan, 1) → (1, RIGHT, scan)
(scan, _) → (_, LEFT,  carry)
(carry,1) → (0, LEFT,  carry)
(carry,0) → (1, LEFT,  halt)

Чому щось таке просте може обчислювати все

Машина не має вбудованого арифметичного, пам'яті за межами стрічки, і жодного уявлення про числа, цикли чи змінні — все це доводиться кодувати як символи та стани. Проте Тюрінг показав, що цей простий механізм може моделювати будь-яку іншу машину Тюрінга за наявності опису її на стрічці (універсальна машина Тюрінга), а Церкль і Тюрінг незалежно стверджували, що все, що людина може обчислити, дотримуючись алгоритму, може обчислити машина Тюрінга — теорема Церква-Тюрінга. Не було знайдено жодної моделі обчислень сильнішої за цю; будь-яка загальна мова програмування, незалежно від того, як вона виглядає, доводиться еквівалентною з точки зору того, що вона може обчислити.

The halting problem

Turing’s paper is really about a negative result. He proved that no algorithm can decide, for every possible machine and input, whether that machine will eventually halt or run forever. The proof is a diagonal argument: assume a halting-decider H exists, then build a machine that asks H about itself and does the opposite of whatever H predicts — a contradiction, so H cannot exist. This single result underlies why compilers cannot always detect infinite loops, why some program-verification questions are provably unsolvable, and why the Game of Life’s long-term behaviour is undecidable in general (it can simulate a Turing machine).

Busy beavers: the price of simplicity

If you restrict a Turing machine to a tiny number of states, how much can it still do before it halts? The busy beaver function BB(n) asks for the maximum number of steps (or 1s written) that an n-state, 2-symbol machine can produce before halting, among all machines that do halt. BB(1)=1, BB(2)=6, BB(3)=21, BB(4)=107 are known exactly; BB(5) was only pinned down in 2024, after decades of search, at 47,176,870 steps. Beyond that the function grows faster than any computable function — computing it exactly is equivalent to solving the halting problem, so BB(n) is itself formally uncomputable for large enough n. A handful of extra states buys an almost unbounded amount of possible behaviour.

What the simulator on this site runs

The five built-in programs are all small, hand-designed transition tables: binary increment (carry propagation across bits, shown above), unary addition (merging two runs of marks into one), a palindrome checker (walking inward from both ends of the tape and comparing symbols), string copy (shuttling a marker back and forth to duplicate a block), and the 3-state busy beaver, which despite only three states and two symbols manages to write six 1s before halting — the maximal such machine, proved optimal by exhaustive search decades ago.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Turing Machine і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.