Turingmachine: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
→Het concept: uitbreiding |
Linkfix ivm sjabloonnaamgeving met AWB |
||
Regel 1:
{{Zijbalk complexiteit en berekenbaarheid}}
In de [[informatica]] is de '''Turingmachine''' een model van berekening en [[berekenbaarheid]], ontwikkeld door de [[wiskunde|wiskundige]] [[Alan Turing|Alan M. Turing]] in zijn beroemde artikel "On computable numbers, with an application to the Entscheidungsproblem" uit [[1936]]-[[1937|37]].
Regel 14:
{| align=center
|[[
|-
| align=center|De Turingmachine
Regel 36:
:Herhaal totdat we in accepterende of afwijzende toestand zijn:
:#Lees het karakter van de band op de plaats van de kop.
:#Is de toestand Qb:<br />- Is dit karakter een '0' of '1', schrijf er dan een '1' voor in de plaats, verplaats de kop naar rechts en blijf in toestand Qb.<br />- Is dit karakter 'leeg', schrijf er dan een 'leeg' karakter voor in de plaats, verplaats de kop naar links en ga naar toestand Q0.<br />Is de toestand Q0:<br />- Is dit karakter een '1', schrijf er dan een 'leeg' karakter voor in de plaats, verplaats de kop naar links en ga naar de accepterende toestand.<br />- Is dit karakter een '0' of 'leeg', schrijf er dan een 'leeg' karakter voor in de plaats en ga naar de afwijzende toestand.
Zoals hieronder gedemonstreerd, is dit een correcte optelling.
{| align=center
|[[
|-
| align=center|2 + 3 = 5
Regel 119:
{{Bronnen|bronvermelding=
* [http://www.abelard.org/turpap2/tp2-ie.asp On computable numbers, with an application to the Entscheidungsproblem]<br />A.M. Turing
* '''Introduction to the theory of computation'''<br />Michael Sipser<br />PWS Publishing Company<br />ISBN 053494728X
* '''An introduction to formal languages and automata''', Second edition<br />Peter Linz<br />D.C. Heath and Company<br />ISBN 0-669-35403-1
}}
| |||