Ce face ca un limbaj să fie complet Turing?

A Turing tarpit este un fel de limbaj ezoteric de programare care se străduiește să fie complet Turing în timp ce folosește cât mai puține elemente posibil. Brainfuck este probabil cel mai cunoscut tarpit, dar există multe.

• Iota și Jot sunt limbaje funcționale cu două și, respectiv, trei simboluri, bazate pe Calculator SK (I) combinator .

• OISC ( Un computer set de instrucțiuni ) denotă un tip de calcul imperativ care necesită o singură instrucțiune din unul sau mai multe argumente, de obicei „scădeți și ramificați dacă este mai mic sau egal cu zero” sau „Retrageți și scăpați dacă împrumutați”. MM86 x86 implementează instrucțiunea anterioară și, prin urmare, este completă Turing.

În general, pentru un limbajul imperativ pentru a fi complet Turing, are nevoie de:

1. O formă de repetare condițională sau salt condițional (de exemplu, while, if + goto)

2. O modalitate de a citi și scrie o formă de stocare (de ex. , variabile, bandă)

Pentru ca un limbaj funcțional bazat pe lambda-calculus să fie TC, acesta are nevoie de:

1. Abilitatea de a abstra funcții peste argumente (de exemplu, abstractizare lambda, citat)

2. Capacitatea de a aplica funcții la argumente (de exemplu, reducere)

Există desigur și alte moduri de a privi calculul, dar acestea sunt modele comune pentru tarpiturile Turing. Rețineți că computerele reale nu sunt nu mașini Turing universale deoarece nu au spațiu de stocare nelimitat. Strict vorbind, acestea sunt „mașini de stocare delimitate”. Dacă ai continua să le adaugi memorie, ei s-ar apropia asimptotic de mașinile Turing aflate la putere. Cu toate acestea, chiar și mașinile de stocare delimitate și mașinile cu stări finite sunt utile pentru calcul; pur și simplu nu sunt universale .

Strict vorbind, I / O nu este necesară pentru completarea Turing; TC afirmă doar că o limbă poate calcula funcția dorită, nu că îți poate arăta rezultatul. În practică, fiecare limbaj util are un mod de a interacționa cu lumea cumva.

Comentarii

• Pentru limbile imperative, sunt suficiente variabilele simple? Am avut impresia că ar fi necesar un fel de colecție (de exemplu, tablouri sau liste legate).
• @luiscubal trebuie să puteți specifica o cantitate arbitrară de date. Cu variabile simple puteți reprezenta cantitatea de date pe care o au variabilele în sine. Ce se întâmplă dacă trebuie să reprezentați N + 1 date diferite. S-ar putea argumenta că, cu trucuri , cum ar fi jocurile Fractran, ați putea face acest lucru chiar și în variabile simple … dar că ‘ nu este exact ceea ce ‘ solicitați.
• Nu este necesar ‘ pentru a fi necesar ca limba să fie acceptată Bucle ENDLESS ?
• Re, ” fiecare limbaj util are un mod de a interacționa cu lumea. ” Algol 60 nu avea un mod definit de interacțiune cu lumea. Toate I / O-urile dvs. dintr-un program Algol 60 au fost realizate apelând funcțiile bibliotecii, iar funcțiile bibliotecii ar putea fi complet diferite în diferite implementări. Însă, mă abțin de la orice discuție dacă Algol 60 a fost ” util sau nu. ”

Din punct de vedere mai practic: dacă puteți traduce toate programele într-o limbă completă Turing în limba dvs., atunci (în măsura în care Știu), limba dvs. trebuie să fie completă.Prin urmare, dacă doriți să verificați dacă un limbaj pe care l-ați proiectat este complet Turing, puteți scrie pur și simplu un Brainf *** în compilatorul YourLanguage și să demonstrați / demonstrați că poate compila toate programele legale BF.

To clarificați, vreau să spun că, pe lângă un interpret pentru YourLanguage, scrieți un compilator (în orice limbă) care poate compila orice program BF în YourLanguage (păstrând aceeași semantică, desigur).

Comentarii

• Da, cu siguranță acesta ar fi cel mai practic mod de abordare. </sarcasm>
• @RobertHarvey are un punct, dar ideea generală este destul de vitală. Brainfuck-ul este dovedit a fi complet complet și foarte simplu pe măsură ce limbajele de programare merg. Pentru limbaje de programare ne-ezoterice, implementarea unui interpret de brainfuck poate fi mult mai ușoară și mai rapidă decât oferirea unei dovezi riguroase de nicăieri (pot implementa BF în câteva linii de Python, dar eu ‘ m nu sunt sigur de unde să încep cu o dovadă formală că Python este complet); și zeci de limbaje ezoterice inspirate de dracu sunt cunoscute ca fiind complete, deoarece ‘ știe cum se hărțuiesc să tragă la cap.
• @RobertHarvey: De ce nu? Cu siguranță, cineva care își proiectează propria limbă ar fi capabil să scrie un compilator BF (dacă era imperativ și să găsească o altă limbă potrivită în alt mod).
• @delnan: Tu vei totuși, trebuie să demonstrați că interpretul dvs. BF implementează corect specificația BF, IOW va trebui să demonstrați că interpretul dvs. BF este, de fapt, un interpret BF și nu un interpret pentru un limbaj asemănător BF care ar putea sau nu să fie Turing-complet.
• @ DarekNędza, ‘ este doar o consecință naturală a modului în care este definită completitudinea Turing; orice extensie a unui limbaj Turing Complete va fi în continuare Turing Complete.

Un sistem poate fi luat în considerare doar să fie complet Turing dacă poate face orice poate face o mașină universală Turing. Deoarece se spune că mașina universală Turing este capabilă să rezolve orice funcție calculabilă dată în timp, sistemele complete Turing pot, prin extensie, să o facă și ele.

Pentru a verifica dacă ceva este complet Turing, vezi dacă poate implementa o mașină Turing în interiorul său. Cu alte cuvinte, verificați dacă poate simula următoarele:

1. Capacitatea de a citi și scrie „variabile” (sau date arbitrare) : Se explică destul de mult.
2. Capacitatea de a simula mișcarea capului de citire / scriere : Nu este suficient pentru a putea prelua și stoca variabile. De asemenea, trebuie să fie posibilă simularea capacității de a muta capul benzii pentru a face referire la alte variabile. Acest lucru poate fi adesea simulat în limbaje de programare cu utilizarea structurilor de date matrice (sau echivalent) sau, în cazul anumitor limbaje, cum ar fi codul mașinii, capacitatea de a face referire la alte variabile prin utilizarea „pointerilor” (sau echivalent).
3. Capacitatea de a simula o mașină cu stări finite : Deși nu sunt menționate des, mașinile Turing sunt de fapt o variația mașinilor cu stări finite utilizate adesea în dezvoltarea AI. Alan Turing a spus că scopul statelor este de a simula diversele moduri de rezolvare a problemelor „unei persoane”.
4. O stare de „stop” : Deși este adesea menționat un set de reguli trebuie să fie capabil să se repete pentru a putea fi considerat complet Turing, acesta nu este într-adevăr un bun criteriu, deoarece definiția formală a algoritmul este starea, algoritmii trebuie să se încheie întotdeauna. Dacă nu pot concluziona într-un fel, fie nu este Turing complet, fie algoritmul menționat nu este o funcție calculabilă. Utilizarea unor sisteme complete care din punct de vedere tehnic nu se pot încheia datorită modului lor de funcționare (cum ar fi consolele de jocuri, de exemplu) depășesc această limitare, putând „simula” o stare de oprire într-o anumită manieră. „, o funcție indecidabilă care demonstrează că este imposibil să construiești un sistem care ar putea detecta cu 100% fiabilitate dacă o anumită intrare va face ca un alt sistem să nu se încheie.

Acestea sunt adevăratul minim cerințele pentru ca un sistem să fie considerat complet Turing. Nimic mai mult, nimic mai puțin. Dacă nu poate simula oricare dintre acestea într-un mod, nu este complet Turing. Metodele propuse de alți oameni sunt doar mijloace până la capăt, deoarece există mai multe sisteme complete Turing care nu au acele caracteristici.

Rețineți că nu există o modalitate cunoscută de a construi un adevărat sistem complet Turing. Acest lucru se datorează faptului că nu există o modalitate cunoscută de a simula cu adevărat nelimitarea benzii mașinii Turing în spațiul fizic.

Un limbaj de programare este complet dacă puteți face orice calcul cu acesta.Nu există un singur set de caracteristici care să facă o limbă completă, astfel încât răspunsurile spunând că aveți nevoie de bucle sau că aveți nevoie de variabile sunt greșite, deoarece există limbi pe care nu le are nici dar sunt completate.

Alan Turing a făcut mașina universală de turing și dacă puteți traduce orice program conceput să funcționeze pe mașina universală pentru a rula în limba dvs., Turing este complet. Acest lucru funcționează și indirect, astfel încât să puteți spune că limbajul X este completat dacă toate programele pentru limbajul complet Y pot fi traduse pentru X, deoarece toate programele mașinii de turing universale pot fi traduse într-un program Y.

Complexitatea timpului , complexitatea spațiului, formatul de intrare / ieșire ușor și ușor de scris orice program nu este inclus în ecuație, astfel încât o astfel de mașină poate efectua teoretic toate calculele dacă calculele nu sunt oprite de pierderea de putere sau dacă Pământul este înghițit de soare.

De obicei, pentru a demonstra completitudinea, ei fac un interpret pentru orice limbă completă dovedită, dar pentru ca aceasta să funcționeze, aveți nevoie de mijloace de intrare și ieșire, două lucruri care nu sunt într-adevăr necesare pentru ca o limbă să fie completă. Este suficient ca programul dvs. să o modifice la starea sa la pornire și să puteți inspecta memoria după oprirea programului.

Pentru a face un limbaj de succes, este nevoie de mai mult decât completarea completă și acest lucru este adevărat chiar pentru prelucrarea tarpiturilor. Nu cred că BrainFuck ar fi fost popular fără , și ..

Comentarii

• ” Un limbaj de programare este complet dacă puteți face orice calcul cu ea. ” Aceasta ‘ este teza Bisericii-Turing, nu ceea ce face ca un limbaj să fie complet Turing.
• @Rhymoid Deci vrei să spui că nimic nu este complet dacă nu poți face un interpret? Adică calculul lambda nu este complet, chiar dacă ‘ este egal?
• Eu ‘ încă mai caut o definiție autoritară a termenilor echivalent Turing și Turing-complet (și Turing-puternic). I ‘ Am văzut deja prea multe cazuri, de la persoane de pe panourile de mesaje la cercetători în propriile lor lucrări ‘, care interpretează acești termeni diferit.
• Oricum, Interpretez ‘ Turing-complete ‘ ca fiind o simulare echivalentă cu o Mașină de Turing Universal (UTM; care, la rândul său, este capabil să simuleze orice mașină Turing – prin urmare ‘ universal ‘). În ziarul lui Turing ‘ din 1936, unde și-a prezentat mașinile, el a definit noțiunea de UTM și a dat o schiță a unei dovezi că UTM-urile sunt echivalente cu simularea Bisericii ‘ s lambda calculus. Procedând astfel, el a dovedit că aveau aceeași putere de calcul. Teza Church-Turing afirmă, pur și simplu, că ” că ‘ este toată puterea de calcul pe care o ‘ voi primi vreodată „.
• Are două definiții formale pentru Pagina de completare a Turing din Wikipedia . Unul necesită I / O, celălalt nu ‘ t. Cel care nu ‘ nu spune că o mașină este completă dacă poate calcula fiecare funcție calculabilă Turing. Acest lucru readuce calculul lambda la finalizarea turing, deoarece puteți face cu ușurință un program egal în calculul lambda care calculează la fel ca orice program de mașină turing.

Nu poți să-ți dai seama dacă va „face o buclă infinită sau se va opri.

————-

Explicație: Având o anumită contribuție, este imposibil să se spună în fiecare caz (folosind o altă mașină Turing) dacă lucrul se va bucla la infinit sau, în cele din urmă, se va opri, cu excepția executării acestuia (ceea ce vă oferă un răspuns dacă o face opriți-vă, dar nu dacă se bucură!).

Acest lucru înseamnă că trebuie să puteți stoca o cantitate potențial nelimitată de date într-un fel – trebuie să existe un echivalent cu banda infinită, indiferent de modul în care complicat! (În caz contrar, există doar un număr finit de stări și atunci puteți verifica dacă ați trecut anterior prin această stare și, eventual, opriți-vă). În general, mașinile Turing pot crește sau micșora dimensiunea stării lor prin unele mijloace controlabile.

Deoarece mașina Turing originală universală Turing are o problemă de oprire de nerezolvat, propria mașină completă Turing trebuie să aibă și o oprire de nerezolvat problemă.

Sistemele complete Turing pot emula orice alt sistem complet Turing, deci dacă puteți construi un emulator pentru un sistem Turing complet bine cunoscut din sistemul dvs., acest lucru dovedește că sistemul dvs. este și Turing complet.

De exemplu, să presupunem că doriți să demonstrați că Snakes & Ladders este completat de Turing, având o placă cu un model de grilă repetat infinit (cu o versiune diferită deasupra și partea stângă). Știind că mașina Minsky cu 2 contoare este completă Turing (care are 2 contoare nelimitate și 1 stare dintr-un număr finit), puteți construi o placă echivalentă în care poziția X și Y pe grilă este valoarea curentă a celor 2 contoare iar calea actuală este starea actuală. Bang! Tocmai ați demonstrat că Snakes & Scările sunt completate.

Comentarii

• Nu ‘ nu cumpărați acest argument. Doar pentru că problema de oprire este indecidabilă pentru mașinile Turing nu implică în mod direct că fiecare notație care vă permite să specificați un program pentru care problema de oprire este indecidabilă este Turing completă. Numai inversul este evident adevărat: dacă notația este completă Turing, atunci este bineînțeles posibil să scrieți programe pentru care problema de oprire este indecidabilă.
• Este ‘ este o condiție necesară. Dacă puteți decide pentru fiecare program dacă se oprește, limba nu este ‘ Turing completată.

O condiție necesară este o buclă cu un număr maxim de iterații care nu este determinat înainte de iterație sau recursivitate în care adâncimea maximă de recursivitate nu este determinată înainte. De exemplu, pentru … în … buclele, pe măsură ce le găsiți în multe limbi mai noi, nu sunt suficiente pentru ca limbajul să fie complet (dar vor avea și alte mijloace). Rețineți că acest lucru nu înseamnă un număr limitat de iterații sau adâncime recursivă limitată, dar că iterațiile maxime și adâncimea recursivă trebuie calculate înainte.

De exemplu, funcția Ackermann nu poate fi calculată într-o limbă fără aceste caracteristici. Pe de altă parte, o mulțime de programe extrem de complexe și extrem de utile pot fi scrise fără a necesita aceste caracteristici.

Pe de altă parte, cu fiecare număr de iterații și fiecare adâncime de recursivitate calculată înainte, nu numai se poate decide dacă un program se va opri sau nu, dar se va opri.

Știu că acesta nu este răspunsul corect din punct de vedere formal, dar odată ce scoateți „minimul” din „Turing-complete” și puneți „practic” la locul său, veți vedea cele mai importante caracteristici care disting un limbaj de programare de un limbaj de marcare sunt

• variabile
• condiționale (dacă / atunci …)
• buclă (buclă / pauză, în timp ce …)

următoarea com e

• funcții anonime și denumite

pentru a testa aceste afirmații, începeți cu un limbaj de marcare, să zicem, HTML. am putea inventa un HTML + numai cu variabile, sau numai condiționale (MS a făcut asta cu comentarii condiționate), sau un fel de construcție de buclă (care, în absența condiționalelor, ar ajunge probabil ca ceva de genul <repeat n="4">...</repeat>). dacă faceți oricare dintre acestea, HTML + va fi semnificativ (?) mai puternic decât HTML simplu, dar ar fi totuși mai mult un markup decât un limbaj de programare; cu fiecare caracteristică nouă, o faceți mai puțin un limbaj declarativ și mai mult un imperativ.

Căutarea minimalității în logică și programare sigură este importantă și interesantă, dar dacă ar fi trebuit să învăț n00bici tineri sau bătrâni „ce programează” și „cum să înveți să programezi”, aș începe cu greu cu lățimea și lățimea completă a fundamentelor teoretice ale completitudinii Turing. întreaga esență a gătitului și a programării face lucruri, în ordinea corectă, repetând până când sunt gata, așa cum a făcut-o mama ta. asta înseamnă totul pentru mine.

apoi, din nou, nu mi-am terminat niciodată CS-ul.

Comentarii

• Dacă nu sunteți sigur, ar trebui să îl cercetați mai întâi. fractran este completat , la fel ca și brainf * ck . Rețineți, de asemenea, că html 5 + CSS 3 este completat, deoarece poate implementa regula 110 .
• da, da, știu. dar toate exemplele date sunt mai mult sau mai puțin ezoterice (deși poate interesante sau surprinzătoare), m Răspunsul a fost unul pragmatic și, probabil, deloc minim. Cred că este ‘ important să subliniem acest lucru – această pagină era numărul 1 când căutam Turing-completeeness pe google, răspunsurile aici sunt IMHO de puțin folos pentru, să zicem, un n00bie cine vrea să știe ce diferențiază HTML de PHP sau Python. Adică, brainf ck nu se numește brainf ck fără niciun motiv.