Turing fuldstændighed - Turing completeness

For brug af dette udtryk i teorien om relativ beregning ved hjælp af orakelmaskiner, se Turing -reduktion .

I beregningsteorien siges et system med databehandlingsregler (såsom en computers instruktionssæt , et programmeringssprog eller en mobilautomat ) at være Turing-komplet eller beregningsmæssigt universelt, hvis det kan bruges til at simulere enhver Turing-maskine . Det betyder, at dette system er i stand til at genkende eller bestemme andre datasæt-regelsæt. Turing-fuldstændighed bruges som en måde at udtrykke kraften i et sådant datasættet regelsæt. Stort set alle programmeringssprog i dag er Turing-komplette. Konceptet er opkaldt efter den engelske matematiker og computerforsker Alan Turing .

Et beslægtet begreb er Turing -ækvivalens  - to computere P og Q kaldes ækvivalente, hvis P kan simulere Q, og Q kan simulere P. Kirken -Turing -tesen formoder, at enhver funktion, hvis værdier kan beregnes af en algoritme, kan beregnes af en Turing-maskine, og derfor at hvis en computer i den virkelige verden kan simulere en Turing-maskine, er det Turing svarende til en Turing-maskine. En universel Turing-maskine kan bruges til at simulere enhver Turing-maskine og i forlængelse heraf beregningsmæssige aspekter af enhver mulig computer i den virkelige verden.

For at vise, at noget er Turing-komplet, er det nok at vise, at det kan bruges til at simulere noget Turing-komplet system. For eksempel er et imperativt sprog Turing-komplet, hvis det har betinget forgrening (f.eks. "Hvis" og "gå" -udsagn eller en "gren, hvis nul" -instruktion; se computer med én instruktion ) og evnen til at ændre en vilkårlig mængde hukommelse (f.eks. evnen til at opretholde et vilkårligt antal dataelementer). Selvfølgelig kan intet fysisk system have uendelig hukommelse; men hvis begrænsningen af ​​begrænset hukommelse ignoreres, er de fleste programmeringssprog ellers Turing-komplette.

Ikke-matematisk brug

I daglig tale bruges udtrykkene "Turing-complete" og "Turing-equivalent" til at betyde, at enhver almindelig computer eller edb-sprog i den virkelige verden tilnærmelsesvis kan simulere beregningsmæssige aspekter af enhver anden computer i den virkelige verden eller computersprog.

Virkelige computere, der er konstrueret indtil nu, kan funktionelt analyseres som en enkeltbånds Turing-maskine ("båndet" svarende til deres hukommelse); dermed kan den tilhørende matematik anvende ved at abstrahere deres operation langt nok. Imidlertid har rigtige computere begrænsede fysiske ressourcer, så de er kun lineært afgrænsede automat færdige. I modsætning hertil er en universel computer defineret som en enhed med et Turing-komplet instruktionssæt, uendelig hukommelse og uendelig ledig tid.

Formelle definitioner

I beregningsteorien bruges flere nært beslægtede udtryk til at beskrive beregningskraften i et beregningssystem (såsom en abstrakt maskine eller programmeringssprog ):

Turing fuldstændighed
Et beregningssystem, der kan beregne alle Turing- beregningsfunktioner, kaldes Turing-complete (eller Turing-kraftfuld). Alternativt er et sådant system et, der kan simulere en universel Turing -maskine .
Turing ækvivalens
Et Turing-komplet system kaldes Turing-ækvivalent, hvis hver funktion det kan beregne også er Turing-beregningsbar; dvs. den beregner præcis den samme klasse af funktioner som Turing -maskiner . Alternativt er et Turing-ækvivalent system et, der kan simulere og simuleres af en universel Turing-maskine. (Alle kendte fysisk implementerbare Turing-komplette systemer er Turing-ækvivalente, hvilket tilføjer støtte til kirken – Turing-tesen .)
(Computational) universalitet
Et system kaldes universelt med hensyn til en systemklasse, hvis det kan beregne alle funktioner, der kan beregnes af systemer i den klasse (eller kan simulere hvert af disse systemer). Typisk bruges udtrykket universalitet stiltiende med hensyn til en Turing-komplet systemklasse. Udtrykket "svagt universel" bruges undertiden til at skelne mellem et system (f.eks. En mobilautomat ), hvis universalitet kun opnås ved at ændre standarddefinitionen af Turing -maskine for at inkludere inputstrømme med uendeligt mange 1'er.

Historie

Turing-fuldstændighed er vigtig, idet ethvert virkeligt design til en computerenhed kan simuleres af en universel Turing-maskine . De Church-Turing-tesen hedder, at det er en lov om matematik - at en universel Turing maskine kan i princippet udføre enhver beregning, at en hvilken som helst anden programmerbar computer kan. Dette siger intet om den indsats, der er nødvendig for at skrive programmet , eller den tid, det kan tage for maskinen at udføre beregningen, eller evner, maskinen kan besidde, som ikke har noget at gøre med beregning.

Charles Babbage 's analytiske motor (1830'erne) ville have været den første Turing-komplet maskine, hvis det var blevet bygget på det tidspunkt, det blev designet. Babbage forstod, at maskinen var i stand til store beregninger, herunder primitive logiske ræsonnementer, men han forstod ikke, at ingen anden maskine kunne gøre det bedre. Fra 1830'erne til 1940'erne blev der bygget og forbedret mekaniske beregningsmaskiner såsom addere og multiplikatorer, men de kunne ikke udføre en betinget gren og var derfor ikke Turing-komplette.

I slutningen af ​​1800 -tallet formulerede Leopold Kronecker forestillinger om beregningsbarhed og definerede primitive rekursive funktioner . Disse funktioner kan beregnes ved hjælp af rote -beregning, men de er ikke nok til at lave en universel computer, fordi instruktionerne, der beregner dem, ikke tillader en uendelig sløjfe. I begyndelsen af ​​det 20. århundrede ledede David Hilbert et program for at aksiomatisere al matematik med præcise aksiomer og præcise logiske fradragsregler, der kunne udføres af en maskine. Snart blev det klart, at et lille sæt fradragsregler er nok til at producere konsekvenserne af ethvert sæt aksiomer. Disse regler blev bevist af Kurt Gödel i 1930 for at være nok til at producere alle sætninger.

Den faktiske opfattelse af beregning blev isoleret kort tid efter, begyndende med Gödels ufuldstændighedssætning . Denne sætning viste, at aksiomsystemer var begrænsede, når de ræsonnerer om beregningen, der udleder deres sætninger. Kirke og Turing demonstrerede uafhængigt af hinanden, at Hilberts Entscheidungsproblem (beslutningsproblem) var uløseligt og identificerede dermed beregningskernen i ufuldstændighedssætningen. Dette arbejde fastslog sammen med Gödels arbejde med generelle rekursive funktioner , at der er sæt enkle instruktioner, som, når de er sat sammen, er i stand til at producere enhver beregning. Gödel's arbejde viste, at begrebet beregning i det væsentlige er unikt.

I 1941 færdiggjorde Konrad Zuse computeren Z3 . Zuse var ikke bekendt med Turings arbejde med beregning på det tidspunkt. Især Z3 manglede dedikerede faciliteter til et betinget spring, hvilket forhindrede den i at blive Turing komplet. Men i 1998 blev det vist af Rojas, at Z3 er i stand til betingede spring, og derfor Turing komplet, ved at bruge nogle af dens funktioner på en utilsigtet måde.

Beregningsteori

Computability theory anvender beregningsmodeller til at analysere problemer og afgøre, om de kan beregnes og under hvilke omstændigheder. Det første resultat af beregningsteori er, at der eksisterer problemer, som det er umuligt at forudsige, hvad et (Turing-komplet) system vil gøre over en vilkårlig lang tid.

Det klassiske eksempel er standsningsproblemet : Opret en algoritme, der tager et input til et program i et hvilket som helst Turing-komplet sprog og nogle data, der skal føres til det program, og bestemmer, om programmet, der fungerer på input, i sidste ende vil stoppe eller vil fortsætte for evigt. Det er trivielt at oprette en algoritme, der kan gøre dette for nogle input, men umuligt at gøre dette generelt. For enhver egenskab ved programmets eventuelle output er det umuligt at afgøre, om denne egenskab holder.

Denne umulighed giver problemer, når man analyserer virkelige computerprogrammer. For eksempel kan man ikke skrive et værktøj, der helt beskytter programmerere mod at skrive uendelige sløjfer eller beskytter brugere mod at levere input, der ville forårsage uendelige sløjfer.

Man kan i stedet begrænse et program til kun at udføre i et bestemt tidsrum ( timeout ) eller begrænse strømmen til flowkontrolinstruktioner (f.eks. Kun give sløjfer, der gentages over elementerne i et eksisterende array). Imidlertid viser en anden sætning, at der er problemer, der kan løses ved hjælp af Turing-komplette sprog, der ikke kan løses af ethvert sprog med kun begrænsede looping-evner (dvs. ethvert sprog, der garanterer, at hvert program i sidste ende stopper). Så et sådant sprog er ikke Turing-komplet. For eksempel kan et sprog, hvor programmer garanteret fuldender og stopper, ikke beregne den beregningsfunktion, der frembringes af Cantors diagonale argument på alle beregningsfunktioner på det pågældende sprog.

Turing orakler

Hovedartikel: Oracle -maskine

En computer med adgang til et uendeligt bånd af data kan være mere kraftfuld end en Turing-maskine: for eksempel kan båndet indeholde løsningen på stoppeproblemet eller et andet Turing-uafklareligt problem. Sådan et uendeligt bånd af data kaldes et Turing -orakel . Selv et Turing -orakel med tilfældige data kan ikke beregnes ( med sandsynlighed 1 ), da der kun er utallige mange beregninger, men utallige mange orakler. Så en computer med et tilfældigt Turing -orakel kan beregne ting, som en Turing -maskine ikke kan.

Digital fysik

Se også: Kirke -Turing -afhandling § Filosofiske implikationer

Alle kendte fysiske love har konsekvenser, der kan beregnes ved en række tilnærmelser på en digital computer. En hypotese kaldet digital fysik siger, at dette ikke er tilfældigt, fordi selve universet kan beregnes på en universel Turing -maskine. Dette ville indebære, at ingen computer mere kraftfuld end en universel Turing -maskine kan bygges fysisk.

Eksempler

De beregningssystemer (algebraer, beregninger), der diskuteres som Turing-komplette systemer, er beregnet til at studere teoretisk datalogi . De er beregnet til at være så enkle som muligt, så det ville være lettere at forstå beregningsgrænserne. Her er et par:

De fleste programmeringssprog (deres abstrakte modeller, måske med nogle bestemte konstruktioner, der antager begrænset hukommelse udeladt), konventionelle og ukonventionelle, er Turing-komplette. Dette omfatter:

Nogle omskrivningssystemer er Turing-komplette.

Turing -fuldstændighed er en abstrakt evneerklæring frem for en recept på bestemte sproglige funktioner, der bruges til at implementere denne evne. De funktioner, der bruges til at opnå Turing -fuldstændighed, kan være ganske forskellige; Fortran -systemer ville bruge loop -konstruktioner eller muligvis endda gå til udsagn for at opnå gentagelse; Haskell og Prolog, der mangler looping næsten helt, ville bruge rekursion . De fleste programmeringssprog beskriver beregninger på von Neumann -arkitekturer , som har hukommelse (RAM og register) og en kontrolenhed. Disse to elementer gør denne arkitektur Turing-komplet. Selv rene funktionelle sprog er Turing-komplette.

Turing -fuldstændighed i deklarativ SQL implementeres gennem rekursive fælles tabeludtryk . Ikke overraskende er proceduremæssige udvidelser til SQL ( PLSQL osv.) Også Turing-komplette. Dette illustrerer en af ​​grundene til, at relativt kraftfulde ikke-Turing-komplette sprog er sjældne: jo mere kraftfuldt sproget er i første omgang, jo mere komplekse er de opgaver, det anvendes på, og jo hurtigere dets mangel på fuldstændighed bliver opfattet som en ulempe, hvilket fremmer dets forlængelse, indtil den er komplet Turing.

Den ikke-typede lambda-beregning er Turing-komplet, men mange typede lambda-beregninger, herunder System F , er ikke. Værdien af ​​maskinskrivningssystemer er baseret på deres evne til at repræsentere de fleste typiske computerprogrammer, mens der opdages flere fejl.

Regel 110 og Conways Game of Life , begge mobilautomater , er Turing-komplette.

Utilsigtet Turing -fuldstændighed

Nogle spil og anden software er Turing-komplet ved et uheld, dvs. ikke ved design.

Software:

Computerspil:

Sociale medier:

Kortspil:

Nul-person spil (simuleringer):

Beregningssprog:

Computer hardware:

  • x86 MOV instruktion

Biologi:

Ikke-Turing-komplette sprog

Der findes mange beregningssprog, der ikke er Turing-komplette. Et sådant eksempel er sættet med almindelige sprog , der genereres af regulære udtryk, og som genkendes af endelige automater . En mere kraftfuld, men stadig ikke Turing-komplet forlængelse af endelige automater er den kategori af pushdown automater og kontekst-fri grammatikker , der er almindeligt anvendt til at generere parse træer i en indledende fase af programmet kompilering . Yderligere eksempler omfatter nogle af de tidlige versioner af pixel shader -sprogene, der er integreret i Direct3D- og OpenGL -udvidelser.

I alt funktionelle programmeringssprog , f.eks. Velgørenhed og Epigram , er alle funktioner totale og skal afsluttes. Velgørenhed bruger et typesystem og kontrolkonstruktioner baseret på kategoriteori , mens Epigram bruger afhængige typer . Den LOOP sprog er konstrueret således, at det beregner kun de funktioner, der er primitive rekursive . Alle disse beregner korrekte undersæt af de samlede beregningsfunktioner, da det fulde sæt af samlede beregningsfunktioner ikke er beregningsberegneligt . Da alle funktioner på disse sprog er totale, kan algoritmer til rekursivt talbare sæt ikke skrives på disse sprog i modsætning til Turing -maskiner.

Selvom (uskrevet) lambda-beregning er Turing-komplet, er simpelthen ikke skrevet lambda-beregning ikke.

Datasprog

Begrebet Turing -fuldstændighed gælder ikke for sprog som XML , HTML , JSON og YAML , fordi de typisk bruges til at repræsentere strukturerede data, ikke beskrive beregning. Disse kaldes undertiden som markeringssprog eller mere korrekt som "containersprog" eller "databeskrivelsessprog".

Se også

Noter

Referencer

Yderligere læsning

eksterne links