Turing-komplet

I beregnelighed, er et system af data-manipulation regler siges at være Turing fuldstændig eller beregningsmæssigt universelle, hvis det kan bruges til at simulere en enkelt-tapede Turing-maskine. Konceptet er opkaldt efter Alan Turing. Et klassisk eksempel er lambda calculus.

En nært beslægtet begreb er, at Turing ækvivalens - to computere P og Q kaldes Turing svarer hvis P kan simulere Q og Q kan simulere P. Således er en Turing-komplet system er en, der kan simulere en Turing-maskine. Ifølge Kirken-Turing tese, der formodninger, at Turing-maskiner er de mest magtfulde computing maskiner, for hver virkelige verden computer der findes en Turing-maskine, der kan simulere det. Universal Turing-maskiner kan simulere enhver Turing-maskine, og dermed enhver mulig virkelige verden computer.

For at vise, at noget er Turing komplet, er det nok at vise, at det kan bruges til at simulere nogle Turing komplet system. For eksempel, et tvingende sprog er Turing komplet, hvis det har betinget forgrening og evnen til at ændre vilkårlige lagerpladser. Da dette er næsten altid tilfældet, er de fleste hvis ikke alle tvingende sprog Turing komplet, hvis vi ignorerer eventuelle begrænsninger finite hukommelse.

Ikke-matematisk forbrug

I dagligdags brug, udtrykkene "Turing komplet" eller "Turing tilsvarende" bruges til at betyde, at enhver virkelige verden generelle formål computer eller computersprog ca kan simulere alle andre virkelige verden generelle formål computer eller edb-sprog.

Rigtige computere konstrueret hidtil er væsentlige svarer til et enkelt bånd Turing-maskine, og dermed den tilhørende matematik kan anvende ved abstrahere deres drift langt nok. Imidlertid har reelle computere begrænsede fysiske ressourcer, så de kun er lineær afgrænset automat færdig. I modsætning hertil er en universel computer defineret som en enhed med en Turing komplet instruktionssæt, uendelig hukommelse, og uendelig tilgængelige tid.

Formelle definitioner

I beregnelighed er flere nært beslægtede termer bruges til at beskrive den beregningsmæssige effekt af en beregningsmæssige-system:

Historie

Turing fuldstændighed er signifikant i at enhver virkelige verden design for en computerenhed kan simuleres ved en universel Turing-maskine. Kirken-Turing tese, at dette er en lov om matematik - at en universel Turing-maskine kan i princippet udføre en beregning, som enhver anden programmerbar computer kan. Det siger intet om den indsats er nødvendig for at skrive programmet, eller den tid, det kan tage for maskinen at udføre beregningen, eller eventuelle evner maskinen kan besidde, som intet har at gøre med beregning.

Charles Babbage analytiske motor ville have været den første Turing-komplet maskinen, hvis den var blevet bygget på det tidspunkt, det blev designet. Babbage værdsat, at maskinen var i stand til store bedrifter af beregning, herunder primitive logiske ræsonnement, men han gjorde ikke forstå, at ingen anden maskine kunne gøre det bedre. Fra 1830'erne indtil 1940'erne, blev mekaniske regnemaskiner såsom addere og formidlere bygget og forbedret, men de kunne ikke udføre en betinget gren og derfor ikke var Turing komplet.

I slutningen af ​​det 19. århundrede, Leopold Kronecker formulerede forestillinger om beregnelighed, definerer primitive rekursive funktioner. Disse funktioner kan beregnes udenad beregning, men de er ikke nok til at gøre en universel computer, fordi de instruktioner, der beregne dem ikke tillader en uendelig løkke. I det tidlige 20. århundrede, David Hilbert førte et program til axiomatize alle matematik med præcise aksiomer og præcise logiske regler for fradrag, som kunne udføres af en maskine. Snart blev det klart, at et lille sæt af fradrag regler er nok til at producere konsekvenserne af et sæt af aksiomer. Disse regler blev bevist af Kurt Gödel i 1930 at være nok til at producere hver sætning. Gödels fuldstændighed teorem 1930 indeholder implicit en definition af en universel computer, fordi de logiske regler, der virker på nogle aksiomer af aritmetiske sidste ende vil vise sig som en sætning resultatet af en beregning.

Selve begrebet beregning blev isoleret snart efter, startende med Gödels ufuldstændige teorem. Denne læresætning viste, at aksiom systemer var begrænset, når ræsonnement om beregningen, som udleder deres teoremer. Kirke og Turing uafhængigt viste, at Hilbert 's Entscheidungsproblem var uløselige, hvilket identificerer den beregningsmæssige kerne ufuldstændighed teorem. Dette arbejde, sammen med Gödel arbejde på generelle rekursive funktioner, fastslået, at der er sæt af enkle instruktioner, som, når de sættes sammen, er i stand til at producere nogen beregning. Arbejdet med Gödel viste, at begrebet beregning er hovedsagelig unik.

Beregnelighed

Det første resultat af beregnelighed er, at det er umuligt generelt at forudsige, hvad en Turing-komplet program vil gøre over en vilkårligt lang tid. For eksempel er det umuligt at bestemme for hvert program-indgangspar om programmet, der opererer på input, i sidste ende vil stoppe eller vil fortsætte for evigt. Det er umuligt at afgøre, om programmet vil vende tilbage "sande" eller om det vil vende tilbage "false". For enhver karakteristik af programmets endelige output, er det umuligt at afgøre, om denne egenskab vil holde. Dette kan give problemer i praksis, når man analyserer den virkelige verden computerprogrammer. En måde at undgå dette er at skabe programmer til at holde op med at udføre efter en bestemt periode, eller for at begrænse strømmen af ​​flow kontrol instruktioner. Sådanne systemer er ikke Turing komplet ved design.

En anden sætning viser, at der er problemer kan løses ved Turing-komplet sprog, som ikke kan løses af alle sprog med kun begrænset looping evner. Givet en garanteret standse sprog, den beregnelige funktion, som er produceret af cantors diagonalbevis på alle beregnelige funktioner i dette sprog ikke er beregnelige på dette sprog.

Turing-orakler

En computer med adgang til en uendelig bånd af data kan være mere magtfuld end en Turing-maskine: for eksempel, kan båndet indeholder løsningen på det standse problem, eller nogle andre Turing-uafgørbart problem. En sådan et uendeligt bånd af data kaldes en Turing Oracle. Selv en Turing orakel med tilfældige data ikke beregnelige, da der kun er tælleligt mange beregninger, men uncountably mange orakler. Så en computer med en tilfældig Turing orakel kan beregne ting, som en Turing-maskine kan ikke.

Digital fysik

Alle kendte fysiske love har konsekvenser, der er beregnelige af en række tilnærmelser på en digital computer. En hypotese kaldet digitale fysik, at dette er ikke nogen tilfældighed, at det er fordi selve universet er beregnelige på en universel Turing-maskine. Dette ville indebære, at ingen computer mere magtfulde end en universel Turing-maskine kan bygges fysisk.

Eksempler

De beregningsmæssige systemer, der omtales som Turing komplette systemer er bestemt til at studere teoretisk datalogi. De er beregnet til at være så enkel som muligt, således at det ville være lettere at forstå grænserne for beregning. Her er et par:

  • Automater teori
  • Universal Turing-maskine
  • Lambda calculus
  • Formel grammatik
  • Formel sprog
  • Omskrivning systemet
  • Post-Turing-maskiner

De fleste programmeringssprog, konventionelle og ukonventionelle, er Turing-komplet. Dette omfatter:

  • Alle generelle formål sprog i bred anvendelse.
    • Proceduremæssige programmeringssprog som C, Pascal.
    • Objekt-orienterede sprog som Java, Smalltalk.
    • Multi-paradigme sprog som Ada, C ++, Common Lisp, Object Pascal.
  • De fleste sprog ved hjælp af mindre almindelige paradigmer
    • Funktionelle sprog som Lisp og Haskell.
    • Logik programmeringssprog såsom Prolog.
    • Deklarative sprog som XSLT.
    • Esoteriske programmeringssprog, en form for matematisk rekreation, hvor programmører arbejde, hvordan du opnår grundlæggende programmering konstruktioner i en yderst vanskelig, men matematisk Turing-ækvivalent sprog.

Turing-komplet er en abstrakt opgørelse af evne, snarere end en recept af specifikke sproglige træk, der anvendes til at gennemføre denne evne. De faktorer, der benyttes til at opnå Turing fuldstændighed kan være helt anderledes; Fortran systemer ville bruge loop-konstruktioner eller måske endda goto erklæringer for at opnå gentagelse; Haskell og Prolog, mangler looping næsten udelukkende, ville bruge rekursion.

Turing-komplet i deklarativ SQL gennemføres ved rekursive fælles tabeludtryk. Ikke overraskende, er proceduremæssige udvidelser til SQL også Turing komplet. Dette illustrerer en af ​​grundene til relativt kraftige ikke-Turing-komplet sprog er sjældne: jo mere magtfulde sproget er i første omgang, de mere komplekse, er de opgaver, som det er anvendt, og jo før dens mangel på fuldstændighed bliver opfattet som en ulempe, fremme dens forlængelse indtil det er Turing komplet.

Den typebestemt lambda calculus er Turing komplet, men mange har skrevet lambda calculi, herunder System F, er ikke. Værdien af ​​indtastede systemer er baseret på deres evne til at repræsentere mest typiske computerprogrammer samtidig at afsløre flere fejl.

Regel 110 og Conway Game of Life, både cellulære automater, der Turing komplet.

Ikke-Turing-komplet sprog

Mange beregningsmæssige sprog findes der ikke Turing komplet. Et eksempel herpå er det sæt af regulære sprog, mest almindeligt regulære udtryk, der er genereret 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 sprog indlejret i Direct3D og OpenGL udvidelser.

I alt funktionelle programmeringssprog, såsom velgørenhed og epigram, alle funktioner er samlet og skal opsige. Velgørenhed bruger en type system, og kontrol-konstruktioner baseret på kategori teori, mens epigram bruger afhængige typer. LOOP sproget er konstrueret således, at det beregner kun de funktioner, der er primitive rekursive. Alle disse beregne ordentlige delmængder af de samlede beregnelige funktioner, da det fulde sæt af totale beregnelige funktioner er ikke computably enumerable. Også, da alle funktioner i disse sprog er alt, rekursivt enumerable sæt kan ikke afgøres på disse sprog, i modsætning til Turing-maskiner.

Selvom lambda calculus er Turing-komplet, simpelthen indtastet lambda calculus er det ikke.

Data-sprog

Begrebet Turing-fuldstændighed gælder ikke for sprog som XML, HTML, JSON, YAML og S-udtryk, fordi de typisk bruges til at repræsentere strukturerede data, ikke beskrive beregning. Disse er undertiden benævnt kodesprog, eller mere korrekt, som "container sprog" eller "data beskrivelse sprog".

  0   0

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha