Modelul formal
O masina Turing e definita ca un tuplu (Q, Σ, Γ, δ, q0, q_accept, q_reject) unde:
- Q = multimea finita de stari
- Σ = alfabetul de intrare
- Γ = alfabetul benzii (Σ ∪ {blank})
- δ: Q × Γ → Q × Γ × {L, R} = functia de tranzitie
- q0, q_accept, q_reject = stari speciale
Teza Church-Turing
Orice calcul care poate fi efectuat printr-o procedura efectiva (algoritm) poate fi realizat de o masina Turing. Cu alte cuvinte, orice limbaj de programare suficient de expresiv e echivalent cu o masina Turing.
Problema opririi (Halting Problem)
Teorema: Nu exista o masina Turing H care sa decida, pentru orice alta masina M si input w, daca M se opreste pe w.
Demonstratia prin diagonalizare (Cantor): Presupunem ca H exista. Construim masina D care:
- Primeste ca input descrierea unei masini M
- Ruleaza H(M, M)
- Daca H spune ca M se opreste, D intra in buela infinita
- Daca H spune ca M nu se opreste, D se opreste
Acum intrebarea: ce face D(D)? Daca D se opreste, inseamna ca H(D, D) a spus ca D nu se opreste — contradictie. Daca D nu se opreste, inseamna ca H(D, D) a spus ca D se opreste — iar contradictie. Deci H nu poate exista.
Aceasta e prima problema nedecidabila descoperita. A pus bazele teoriei computabilitatii.
Alte probleme nedecidabile
- Problema corespondentei Post
- Determinarea daca o gramatica context-free genereaza toate sirurile posibile
- Probleme cu ecuatii diofantice (al zecelea Hilbert)
- Jocul vietii lui Conway — determinarea daca o configuratie dispare
Masina Turing universala
O masina Turing care poate simula orice alta masina Turing. Primeste ca input (M, w) unde M e descrierea unei masini si w e inputul ei.
Aceasta e baza arhitecturii von Neumann: programul e stocat in memorie ca date. Fara acest concept, calculatoarele moderne nu ar exista.
Limite practice
Desi masina Turing e un model teoretic, limitarile ei au implicatii practice directe:
- Nu poti scrie un program care verifica daca alt program se termina
- Nu poti scrie un program care verifica daca doua functii sunt echivalente
- Nu poti scrie un antivirus perfect