Hva gjør et språk Turing komplett?

A Turing tarpit er et slags esoterisk programmeringsspråk som prøver å være Turing-komplett mens du bruker så få elementer som mulig. Brainfuck er kanskje den mest kjente tarpit, men det er mange.

• Iota og Jot er funksjonelle språk med henholdsvis to og tre symboler, basert på SK (I) kombinatorregning .

• OISC ( One Instruction Set Computer ) betegner en type tvingende beregning som bare krever en instruksjon av ett eller flere argumenter, vanligvis “trekker og forgrener hvis mindre enn eller lik null”, eller “Trekk omvendt og hopp over hvis du låner”. MM86 x86 implementerer den tidligere instruksjonen og er dermed Turing-komplett.

Generelt, for en tvingende språk for å være Turing-komplett, trenger det:

1. En form for betinget repetisjon eller betinget hopp (f.eks. while, if + goto)

2. En måte å lese og skrive noen form for lagring på (f.eks. , variabler, tape)

For at et lambda-calculus -basert funksjonelt språk skal være TC, er det behov:

1. Evnen til å abstrakte funksjoner fremfor argumenter (f.eks. lambda-abstraksjon, sitat)

2. Evnen til å bruke funksjoner på argumenter (f.eks. reduksjon)

Det er selvfølgelig andre måter å se på beregning på, men dette er vanlige modeller for Turing tarpits. Merk at ekte datamaskiner er ikke universelle Turing-maskiner fordi de ikke har ubegrenset lagring. Strengt tatt er de “avgrensede lagringsmaskiner”. Hvis du fortsatte å legge til minne til dem, ville de asymptotisk nærme seg Turing-maskiner ved makten. Imidlertid er selv avgrensede lagringsmaskiner og endelige tilstandsmaskiner nyttige for beregning; de er rett og slett ikke universelle .

Strengt tatt er I / O ikke nødvendig for Turing-fullstendighet; TC hevder bare at et språk kan beregne funksjonen du vil ha, ikke at det kan vise deg resultatet. I praksis har hvert nyttig språk en måte å samhandle med verden på en eller annen måte.

Kommentarer

• Er det enkle variabler nok for viktige språk? Jeg var under inntrykk av at en slags samling (f.eks. Matriser eller koblede lister) ville være nødvendig.
• @luiscubal, du trenger for å kunne spesifisere en vilkårlig mengde data. Med enkle variabler kan du representere datamengden som variablene selv har. Hva om du trenger å representere N + 1 forskjellige data. Man kan hevde at med triks som Fractran spiller, kan du gjøre det selv i enkle variabler … men at ‘ er ikke helt det du ‘ spør.
• Er ikke ‘ t det kreves at språket må støtte ENDELøse sløyfer?
• Re, » ethvert nyttig språk har en måte å samhandle med verden på. » Algol 60 hadde ingen definert måte å samhandle med verden på. All I / O i et Algol 60-program ble gjort ved å ringe biblioteksfunksjoner, og biblioteksfunksjonene kan være helt forskjellige i forskjellige implementeringer. Men jeg henter meg bort fra enhver diskusjon om Algol 60 var » nyttig. »

Fra et mer praktisk synspunkt: hvis du kan oversette alle programmene på et Turing-komplett språk til ditt språk, så (så langt som Jeg vet), språket ditt må være Turing-komplett.Derfor, hvis du vil sjekke om et språk du designet er Turing-komplett, kan du ganske enkelt skrive en Brainf *** til YourLanguage-kompilatoren og bevise / demonstrere at den kan kompilere alle lovlige BF-programmer.

Til klargjøre, jeg mener at i tillegg til en tolk for YourLanguage, skriver du en kompilator (på hvilket som helst språk) som kan kompilere hvilket som helst BF-program til YourLanguage (med samme semantikk, selvfølgelig).

Kommentarer

• Ja, det ville definitivt være den mest praktiske måten å nærme seg det på. </sarcasm>
• @RobertHarvey har et poeng, men den generelle ideen er ganske viktig. Brainfuck har vist seg å være turing-komplett og veldig enkel når programmeringsspråk går. For ikke-esoteriske programmeringsspråk kan det være mye enklere og raskere å implementere en brainfuck-tolk enn å gi et strengt bevis fra ingensteds (jeg kan implementere BF i et par linjer med Python, men jeg ‘ m ikke sikker på hvor jeg skal begynne med et formelt bevis på at Python er fullført); og dusinvis av esoteriske hjernefuckinspirerte språk er kjent for å være fullstendige fordi de ‘ vet hvordan de kartlegges for hjernefuck.
• @RobertHarvey: Hvorfor ikke? Sikkert vil noen som designer sitt eget språk kunne skrive en BF-kompilator til det (hvis det var viktig, og ellers finne et passende annet språk).
• @delnan: Du vil må du imidlertid bevise at BF-tolken din implementerer BF-spesifikasjonen riktig, IOW må du bevise at din BF-tolk faktisk er en BF-tolk og ikke en tolk for et BF-lignende språk som kanskje eller ikke kan være Turing-komplett.
• @ DarekNędza, at ‘ bare er en naturlig konsekvens av hvordan Turing Fullstendighet er definert; enhver utvidelse av et Turing Complete-språk vil fortsatt være Turing Complete.

Et system kan bare vurderes å være Turing komplett hvis den kan gjøre noe en universell Turing-maskin kan. Siden den universelle Turing-maskinen sies å være i stand til å løse hvilken som helst beregningsbar funksjon gitt tid, kan Turing komplette systemer i forlengelse også gjøre det.

For å sjekke om noe er Turing komplett, se om du kan implementere en Turing-maskin inne i den. Med andre ord, sjekk om det kan simulere følgende:

1. Evnen til å lese og skrive «variabler» (eller vilkårlige data) : Ganske mye selvforklarende.
2. Evnen til å simulere flytting av lese- / skrivehodet : Det er ikke nok til å bare kunne hente og lagre variabler. Det må også være mulig å simulere muligheten til å flytte båndets hode for å kunne referere til andre variabler. Dette kan ofte simuleres innen programmeringsspråk med bruk av array-datastrukturer (eller tilsvarende), eller, i tilfelle av visse språk, for eksempel maskinkode, muligheten til å referere til andre variabler ved bruk av «pekere» (eller tilsvarende).
3. Evnen til å simulere en endelig tilstandsmaskin : Selv om det ikke er nevnt ofte, er Turing-maskiner faktisk en variasjon av finite state-maskiner som ofte brukes innen AI-utvikling. Alan Turing sa at formålet med statene er å simulere en persons forskjellige måter å løse problemer på.
4. En «stopp» -stat : Selv om det ofte er nevnt, må et sett med regler kunne gjenta seg for å kunne regnes som Turing fullført, det er egentlig ikke et godt kriterium siden den formelle definisjonen av hva en algoritme er tilstand algoritmer må alltid til slutt konkludere. Hvis de ikke kan konkludere på en eller annen måte, er det ikke Turing fullført, eller er algoritmen ikke en beregningsbar funksjon. Turing komplette systemer som teknisk ikke kan konkludere på grunn av måten de jobber på (som for eksempel spillkonsoller), kommer seg rundt denne begrensningen ved å kunne «simulere» en stoppende tilstand på en eller annen måte. For ikke å forveksle med «stoppproblemet» «, en uavgjørelig funksjon som viser at det er umulig å bygge et system som kan oppdage med 100% pålitelighet hvis en gitt inngang vil føre til at et annet system ikke konkluderer.

Dette er det sanne minimum krav for at et system skal betraktes som Turing komplett. Intet mer, intet mindre. Hvis det ikke kan simulere noen av disse på en eller annen måte, er det ikke Turing fullført. Metodene andre foreslår er bare midler til slutt, da det er flere Turing-komplette systemer som ikke har disse funksjonene.

Merk at det ikke er noen kjent måte å faktisk bygge et ekte Turing-komplett system på. . Dette er fordi det ikke er noen kjent måte å virkelig simulere ubegrensningen av Turing-maskinens bånd i det fysiske rommet.

Et programmeringsspråk er i ferd med å bli fullført hvis du kan gjøre noen beregninger med det.Det er ikke bare ett sett med funksjoner som gjør et språk fullstendig, så svarene sier at du trenger sløyfer eller at du trenger variabler er feil siden det er språk som verken har men er turing fullført.

Alan Turing laget den universelle turingmaskinen, og hvis du kan oversette et hvilket som helst program designet for å fungere på universalmaskinen for å kjøre på språket ditt, er det også Turing complete. Dette fungerer også indirekte, slik at du kan si at språk X turer fullstendig hvis alle programmer for turing fullstendig språk Y kan oversettes til X siden alle universelle turing maskinprogrammer kan oversettes til et Y-program.

Tidskompleksiteten , romkompleksitet, lett inngangs- / utdataformat og enkelt å skrive noe program er ikke inkludert i ligningen, slik at en slik maskin teoretisk kan gjøre alle beregninger hvis beregningene ikke stoppes av strømtap eller jorden blir svelget av solen.

Vanligvis for å bevise turing fullstendighet utgjør de en tolk for alle som har vist seg å være turing fullstendig språk, men for at det skal fungere trenger du inn- og utdata, to ting som virkelig ikke kreves for at et språk skal turing komplett. Det er nok at programmet ditt kan endre tilstanden ved oppstart, og at du kan inspisere minnet etter at programmet er stoppet.

For å lage et vellykket språk trenger det mer enn å tømme fullstendighet, og dette er sant for jevn turing tarpits. Jeg tror ikke BrainFuck hadde vært populært uten , og ..

Kommentarer

• » Et programmeringsspråk er turing komplett hvis du kan gjøre noen beregninger med den. » At ‘ er Church-Turing-avhandlingen, ikke det som gjør et språk Turing-komplett.
• @ Rhymoid Så du mener ingenting er turing komplett med mindre du kan lage tolk? Dvs. lambda-kalkulus er ikke turing komplett selv om den ‘ s turing ekvivalent?
• Jeg ‘ Jeg ser fremdeles etter en autoritativ definisjon av begrepene Turing-ekvivalent og Turing-komplett (og Turing-kraftig). Jeg ‘ Vi har allerede sett for mange tilfeller, fra folk på oppslagstavler til forskere i deres egne friggin ‘ papirer, som tolker disse begrepene annerledes.
• Uansett, Jeg tolker ‘ Turing-komplett ‘ som simulering som tilsvarer en Universal Turing Machine (UTM; som igjen er i stand til å simulere enhver Turing-maskin – derav ‘ universal ‘). I Turing ‘ s papir fra 1936, hvor han introduserte sine maskiner, definerte han forestillingen om en UTM, og ga en skisse av et bevis på at UTM er simulering som tilsvarer kirken ‘ s lambda-beregning. Ved å gjøre dette beviste han at de hadde samme beregningskraft. Church-Turing-avhandlingen hevder, enkelt sagt, at » at ‘ er all beregningskraften du ‘ Får alltid «.
• Den har to formelle definisjoner for Turing-fullstendighetssiden på Wikipedia . Den ene krever I / O, den andre gjør ikke ‘ t. Den som ikke ‘ ikke sier at en maskin turer fullstendig hvis den kan beregne hver funksjon som kan beregnes av Turing. Det setter lambdakalkulus tilbake til å være turing komplett, siden du enkelt kan lage et likeprogram i lambdakalkulus som beregner det samme som alle turingmaskinprogrammer.

Du kan ikke fortelle om det vil gå uendelig eller stoppe.

————-

Forklaring: Gitt noen innspill er det umulig å si noe i alle tilfeller (ved hjelp av en annen Turing-maskin) om tingen kommer til å løkke i det uendelige eller til slutt kommer til å stoppe, bortsett fra ved å kjøre den (som gir deg svar hvis den gjør det) stopp, men ikke hvis det løkker!).

Dette betyr at du må kunne lagre en potensielt ubegrenset mengde data på en eller annen måte – det må tilsvare det uendelige båndet, uansett hvordan innviklet! (Ellers er det bare et endelig antall stater, og så kan du sjekke om du tidligere har vært gjennom den tilstanden og til slutt stoppe). Generelt kan Turing-maskiner vokse eller krympe størrelsen på deres tilstand på noen kontrollerbare måter.

Siden Turing sin originale universelle Turing-maskin har et uløselig stoppproblem, må din egen Turing-komplette maskin også ha en uløselig stopp. problem.

Turing komplette systemer kan etterligne ethvert annet Turing komplett system, så hvis du kan bygge en emulator for et velkjent Turing komplett system i systemet ditt, beviser det at systemet ditt også er Turing komplett.

Anta for eksempel at du vil bevise at Slanger & Stiger er Turing komplett, gitt et brett med et uendelig gjentatt rutenettmønster (med en annen versjon på toppen og venstre side). Å vite at Minsky-maskinen med 2 teller er Turing komplett (som har to ubegrensede tellere og en tilstand ut av et endelig antall), kan du konstruere et tilsvarende kort der X- og Y-posisjonen på rutenettet er den nåværende verdien av de to tellerne. og den nåværende banen er den nåværende tilstanden. Bang! Du har nettopp bevist at Slanger & Stiger er i full tur.

Kommentarer

• Jeg vet ikke ‘ t kjøp argumentet. Bare fordi stoppeproblemet er ubestemmelig for Turing-maskiner, betyr det ikke direkte at hver notasjon som lar deg spesifisere et program som stoppeproblemet er uavgjørelig for, er Turing fullført. Bare det omvendte er åpenbart sant: Hvis notasjonen er Turing fullført, er det selvfølgelig mulig å skrive programmer som det stoppende problemet ikke er avgjørelig for.
• Det ‘ en nødvendig tilstand. Hvis du kan bestemme for hvert program om det skal stoppes, er språket ikke ‘ t Turing fullført.

En nødvendig betingelse er en sløyfe med maksimalt iterasjonstall som ikke er bestemt foran iterasjonen, eller rekursjon der maksimal rekursjonsdybde ikke bestemmes fremover. Som et eksempel, for … i … sløyfer som du finner dem på mange nyere språk, er ikke nok til å gjøre språketuringen komplett (men de vil ha andre midler). Merk at dette ikke betyr et begrenset antall iterasjoner eller begrenset rekursjonsdybde, men at maksimal iterasjon og rekursjonsdybde må beregnes fremover.

For eksempel kan ikke Ackermann-funksjonen beregnes på et språk uten På den annen side kan det skrives mye svært kompleks og svært nyttig programvare uten å kreve disse funksjonene.

På den annen side, med hver iterasjonstelling og hver rekursjonsdybde beregnet fremover, ikke bare kan det avgjøres om et program skal stoppe eller ikke, men det vil stoppe.

jeg vet at dette ikke er det formelt riktige svaret, men når du tar det «minimale» ut av «Turing-complete» og legger «praktisk» tilbake der det hører hjemme, vil du se de viktigste funksjonene som skiller et programmeringsspråk fra et markeringsspråk er

• variabler
• betingede (hvis / da …)
• loopage (loop / break, while …)

neste com e

• anonyme og navngitte funksjoner

for å teste disse påstandene, start med et markeringsspråk, for eksempel HTML. vi kunne finne på en HTML + med bare variabler, eller bare betingelser (MS gjorde det med betingede kommentarer), eller en slags loopkonstruksjon (som i fravær av betingelser sannsynligvis ville ende opp som noe som <repeat n="4">...</repeat>). å gjøre noen av disse vil gjøre HTML + betydelig (?) kraftigere enn vanlig HTML, men det vil fortsatt være mer av en markering enn et programmeringsspråk; med hver nye funksjon gjør du det mindre til et deklarativt og mer av et tvingende språk.

søken etter minimalitet innen logikk og programmering er absolutt viktig og interessant, men hvis jeg måtte lære n00bies unge eller gamle «hva programmerer» og «hvordan lære å programmere», ville jeg knapt starte ut med hele bredden og bredden av det teoretiske grunnlaget for Turing-fullstendighet. hele essensen av matlaging og programmering er å gjøre ting, i riktig rekkefølge, gjenta til det er klart, slik moren din gjorde det. det handler om å oppsummere det for meg.

så igjen, jeg har aldri fullført CS.

Kommentarer

• Hvis du ikke er sikker, bør du undersøke det først. fractran er fullført , som brainf * ck . Merk også at html 5 + CSS 3 er Turing komplett fordi den kan implementere regel 110 .
• ja jeg vet det. men alle eksemplene som er gitt er mer eller mindre esoteriske (mens de kanskje er interessante eller overraskende), m svaret var pragmatisk, og sannsynligvis ikke minimalt i det hele tatt. Jeg tror det ‘ er viktig å påpeke det – denne siden var nr. 1 når vi søkte etter Turing-fullstendighet på google, svarene her er IMHO til liten nytte for for eksempel en n00bie som vil vite hva som skiller HTML fra PHP eller Python. jeg mener, brainf ck kalles ikke brainf ck uten grunn.