Mașină universală de Turing

O mașină Turing este o mașină Turing universală care poate înlocui orice mașină Turing. După ce a primit programul și datele de intrare ca intrare, acesta calculează răspunsul pe care mașina Turing, al cărei program a fost dat ca intrare, l-ar calcula din datele de intrare.

Definiție formală

Programul oricărei mașini Turing deterministe poate fi scris folosind un alfabet finit format din simboluri de stare, paranteze, săgeți și așa mai departe; Să notăm acest alfabet al mașinii ca . Atunci o mașină Turing universală U pentru o clasă de mașini cu un alfabet și k benzi de intrare este o mașină Turing cu k + 1 benzi de intrare și un alfabet astfel încât, dacă primelor k benzi li se dă o valoare de intrare și k + 1 . codul scris corect al unei mașini Turing , atunci U va produce același răspuns ca și pe aceste intrări sau va rula pe termen nelimitat dacă $\Sigma_1$ $\Sigma _{2}$ $\Sigma_1 \cup \Sigma_2$ $M_{1}$ $M_{1}$ $M_{1}$ nu te opri la aceste date.

Teorema mașinii Turing universală afirmă că o astfel de mașină există și modelează alte mașini cu cel mult decelerație pătratică (adică dacă mașina originală a făcut t pași, atunci mașina universală va lua cel mult ct² ). Dovada acestei teoreme este constructivă (o astfel de mașină este ușor de construit, trebuie doar să o descrii cu atenție). Teorema a fost propusă și demonstrată de Turing în 1947 .

Vezi și

Masina de posta
Simulator de automată multiplatformă JFLAP , mașini Turing, gramatică, desen grafic automat