În informatică, o mașină Turing universală (universal Turing machine, UTM) este o mașină Turing care poate simula o mașină Turing arbitrară pe o intrare arbitrară. Mașina universală realizează în esență acest lucru citind atât descrierea mașinii care trebuie simulată, cât și intrarea către mașina respectivă de pe propria bandă. Alan Turing a introdus ideea unei astfel de mașini în 1936–1937. Acest principiu este considerat a fi originea ideii unui computer cu program stocat folosit de John von Neumann în 1946 pentru „Instrumentul de calcul electronic” care poartă acum numele lui von Neumann: arhitectura von Neumann.[1]
În ceea ce privește complexitatea computațională, o mașină Turing universală cu mai multe benzi trebuie să fie mai lentă prin factor logaritmic în comparație cu mașinile pe care le simulează.[2]
Introducere

(Mașina Turing universală.)
Fiecare mașină Turing calculează o anumită funcție calculabilă parțial fixă din șirurile de intrare pe alfabetul său informatic. În acest sens, se comportă ca un computer cu un program fix. Cu toate acestea, putem codifica tabelul de acțiuni al oricărei mașini Turing într-un șir. Astfel, putem construi o mașină Turing care așteaptă pe banda sa un șir care descrie un tabel de acțiuni urmat de un șir care descrie banda de intrare și calculează banda pe care mașina Turing codificată ar fi calculat-o. Turing a descris o astfel de construcție în detaliu complet în lucrarea sa din 1936:
„Este posibil să se inventeze o singură mașină care să poată fi folosită pentru a calcula orice secvență calculabilă. Dacă această mașină U este furnizată cu o bandă la începutul căreia este scris S.D [„descrierea standard” a unui tabel de acțiuni] a unor mașini de calcul M, atunci U va calcula aceeași secvență ca M.”[3]
Referințe
- Martin Davis, The universal computer : the road from Leibniz to Turing (2017)
- Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. secțiunea 1.4, „Machines as strings and the universal Turing machine” și 1.7, „Proof of theorem 1.9”
- Aldinele înlocuiesc scriptul. Turing 1936 în Davis, Martin, ed. (1965). The Undecidable (Reprint ed.). Hewlett, NY: Raven Press. pp. 127–128, cu corecții la UTM a lui Turing de Emil Post cf notei de subsol 11 pg:299. Un exemplu de noțiune a lui Turing despre S.D este dat la sfârșitul acestui articol.
(Include texte traduse și adaptate din Wikipedia de Nicolae Sfetcu)
Lasă un răspuns