Versionen fra 30. mar. 2007, 16:59 redigér RobotQuistnix (diskussion \| bidrag) 116.785 edits m robot Tilføjer: be:Машына Т'юрынга ← Gå til forrige forskel		Versionen fra 2. apr. 2008, 21:21 redigér fjern redigering Villy Fink Isaksen (diskussion \| bidrag) Kontooprettere, Udvidede bekræftede brugere, Patruljanter 83.308 edits fjerner overflødig fedskrift Gå til næste forskel →
Linje 1: En '''Turingmaskine''' er en matematisk model for en simpel symbolmanipulerende maskine som trods sin enkle opbygning kan udføre ikke-trivielle beregninger og simulere logikken i enhver [[computer]]. Turingmaskiner blev først beskrevet af [[Alan Turing]] i [[1936]]. De spiller en central rolle inden for [[datalogi]]en i teorierne vedrørende [[beregnelighed]] og [[kompleksitetsteori\|beregningers kompleksitet]] og generelt i matematisk logik. En Turingmaskine kan være en ~~'''~~''specifik Turingmaskine~~'''~~'' som er konstrueret til at løse et bestemt problem, eller det kan være en ~~'''~~''universel Turingmaskine~~'''~~'' som kan læse en kodet beskrivelse af en vilkårlig Turingmaskine og dennes inputdata, og derefter udføre dens beregninger. ==Uformel beskrivelse== Linje 7: Mere præcist består en Turingmaskine af: # Et '''BÅND''' som er inddelt i celler på en række. Hver celle indeholder et symbol fra et endeligt alfabet. Alfabetet indeholder et specielt ''blank''-symbol og et eller flere andre symboler. Celler som endnu ikke er tilskrevet noget, forudsættes at indeholde det blanke symbol. # Et '''HOVED''' som kan læse og skrive symboler på båndet og rykke sig til højre og venstre på båndet, en celle af gangen. # En '''TABEL''' # Et '''tilstandsregister''' Bemærk at enhver del af maskinen -- dens tilstands- og symbolmængde -- dens mulige skridt -- skrivning, sletning og bevægelse af hoved -- er ''endelig'', ''diskret'' og ''skelnelig''; det er det uendelige bånd som giver den en ubegrænset mængde lagerplads.

Turingmaskine: Forskelle mellem versioner