Turing-complet

În informatică și logică , se spune că un sistem formal este complet în sensul Turing sau Turing-complet (prin urmărirea limbii engleze Turing-complete ) dacă are o putere expresivă cel puțin echivalentă cu cea a mașinilor Turing . Într-un astfel de sistem, este deci posibil să programați orice mașină Turing.

Această noțiune este făcută relevantă de teza Bisericii , care postulează existența unei noțiuni naturale de calculabilitate. Astfel, puterea expresivă a mașinilor Turing coincide cu cea a funcțiilor recursive , a calculului lambda sau chiar a mașinilor de numărare .

Deși unele modele de calcul, numite hipercomputatoare , sunt strict mai expresive decât mașinile Turing, aceste modele sunt obiecte de speculație (care necesită, de exemplu, efectuarea unui număr infinit de operații sau de calculat pe setul de numere. Real) și nu este cunoscut dacă sunt fezabile fizic. În aceste condiții, teza Bisericii presupune universalitatea modelului de calcul al mașinii Turing: orice sistem complet Turing ar fi de fapt echivalent cu mașinile Turing.

Limbaje de programare complete-Turing

La fel ca un model de calcul, un limbaj de calculator se spune că este complet Turing dacă permite reprezentarea tuturor funcțiilor calculabile în sensul lui Turing și Biserică (fără a aduce atingere limitării memoriei computerului).

Unii autori iau această proprietate pentru definirea unui limbaj de programare , dar pot fi alese și alte definiții.

Limbajele obișnuite de programare ( C , Java ...) sunt complete Turing deoarece au toate ingredientele necesare pentru simularea unei mașini universale Turing (numărare, comparare, citire, scriere etc.). Limbajul C ++ este, de asemenea, complet Turing, iar subsetul care permite programarea generică ( șabloane ) este, de asemenea, .

Limbajul SQL , inițial incomplet în sensul lui Turing, a devenit așa cu standardul SQL: 1999 permițându-i să scrie interogări recursive .

Limbajul LaTeX (de la TeX ), destinat compoziției documentelor, este, de asemenea, complet Turing.

Limbajul HTML singur nu este complet Turing, deși s-a dovedit că limbajul CSS (versiunea 3) permite construirea codului automat automat celular 110 (a se vedea regula 110  (in) ), cunoscut ca fiind universal în sensul lui Turing . Aceste două limbaje sunt adesea inseparabile, putem concluziona că HTML + CSS este complet Turing și, prin urmare, această asociere îl face teoretic un limbaj de programare.

Un limbaj complet Turing moștenește caracteristicile unei mașini Turing. De exemplu, problema închiderii este indecidabilă , deci este imposibil să scrieți un program care să spună dacă un program arbitrar dat i se termină sau nu.

Limbi care nu sunt complete Turing

Unele limbi dedicate abordării problemelor specifice nu sunt complete Turing. Sistemul F , un formalism de calcul lambda este un exemplu. Mai mult decât atât - prin proiectare - limbajele totale  (en) , în care toate calculele se încheie în mod necesar (cum ar fi limbajul Gallina al asistentului de probă Coq ), nu sunt nici Turing-complete. Cu toate acestea, aceștia din urmă sunt capabili în practică să calculeze tot ceea ce este de interes, cu alte cuvinte pot implementa toate funcțiile de care am putea avea nevoie în viața practică; calculele care le scapă, fie au o complexitate dincolo de imaginabil și realizabil, fie nu se termină. Compilația trebuie să demonstreze încetarea programelor sau să necesite interacțiunea cu programatorul pentru unele demonstrații, dar acesta este prețul de plătit pentru calitatea codului care este corectă prin construcție.

Exemple în afara limbajelor de programare

Unele jocuri și software sunt completate din întâmplare, fără ca autorii lor să dorească sau să ia în considerare:

Articole similare

Note și referințe

Note

  1. Un computer are memorie finită, modelul mașinii lui Turing are memorie nelimitată.

Referințe

  1. Biroul de traduceri , înregistrarea bazei de date TERMIUM Plus , pe termiumplus.gc.ca ,2 februarie 2017(accesat pe 23 mai 2019 )
  2. (în) John C. Mitchell, Concepts in Programming Languages , Cambridge University Press ,2003( citiți online ) , p.  14 :

    „  Faptul că toate limbajele de programare standard exprimă cu precizie clasa funcțiilor recursive parțiale este adesea rezumat prin afirmația că toate limbajele de programare sunt complete Turing.  "
  3. (în) Bruce J. MacLennan, Principiile limbajelor de programare , Oxford University Press ,1999, Introducere: Ce este un limbaj de programare? :

    „  Un limbaj de programare este un limbaj destinat exprimării programelor de calculator și care este capabil să exprime orice program de computer. Aceasta nu este o noțiune vagă. Există un mod teoretic precis de a determina dacă un limbaj de calculator poate fi folosit pentru a exprima orice program, și anume, arătând că este echivalent cu o mașină universală Turing.  "
  4. (in) „  Nu sunt deloc considerate limbaje complete Turing limbaje de programare?  » , On Stack Exchange La întrebarea adresată, un răspuns selectat consideră că completitudinea Turing nu este necesară pentru a considera un limbaj ca limbaj de programare.
  5. Exemplu de implementare a unei mașini Turing în C: (ro) Juan Pablo Rinaldi (juampi), „  O implementare a unei mașini Turing în C  ” , pe GitHub ,13 ianuarie 2014(accesat pe 21 mai 2019 ) .
  6. „  LaTeX este mai puternic decât crezi - Calculul numerelor Fibonacci și completitudinea Turing - ShareLaTeX, editor online LaTeX  ” , la fr.sharelatex.com (accesat la 2 iunie 2017 ) .
  7. (în) Eli & Jonas, „  CSS3 s-a dovedit a fi„ Turing complet ”  „ pe Accodeing to you (accesat la 17 mai 2019 ) .
  8. „  Despre importanța completitudinii lui Turing  ” pe Lambda Ultimate  (în) .
  9. Benjamin Werner, „  Seturi în tipuri, tipuri în seturi  ”, Proceedings of TACS'97 ,1997.
  10. „Omul folosește cel mai dificil joc de computer din lume pentru a crea ... o mașină de lucru Turing” (versiunea Internet Archive , 27 iunie 2015 ) , la www.themarysue.com ,16 aprilie 2010.
  11. Paul Rendell , „O mașină de Turing în jocul vieții lui Conway” (versiunea Internet Archive , 8 iulie 2009 ) , la rendell-attic.org ,12 ianuarie 2005.
  12. (în) Alex Churchill , „Magic: The Gathering is Turing completeeness” (versiune datată 7 mai 2019 pe Internet Archive ) , de la Universitatea Cornell ,23 aprilie 2019.
  13. (în) Gunivers, „  Data Pack - Universal Turing Machine  ” , pe YouTube ,17 iulie 2019(accesat la 6 mai 2020 ) .
  14. (în) Tom Wildenhain, „  Despre completarea completă a MS PowerPoint  ” pe https://www.andrew.cmu.edu/user/twildenh/ ,16 martie 2017(accesat pe 10 iulie 2020 )
  15. (în) Habbo (@Habbo), „  Știm că sunt talentați Unii Habbos care își propun ca acesta să ia doar tortul! Unul dintre jucătorii noștri @sirjonasxx și-a asumat provocarea de a crea o mașină Turing funcțională în joc și au SUCCES! Hai să verificăm.  » , Pe Twitter ,9 noiembrie 2020(accesat la 30 noiembrie 2020 )

Anexe

Articole similare