Algoritme Les 14

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4

vandaag

• Turing machine
• reguliere expressies
  

Werking De Turingmachine

De kop

De kop leest de informatie die in een vakje staat.

Die informatie én de huidige toestand van de eindige automaat, bepalen in welke nieuwe toestand de eindige automaat terechtkomt.

In bepaalde toestanden zal de eindige automaat ook informatie in het vakje schrijven.

De band

De band bevat de input voor de eindige automaat.

Nadat de automaat klaar is, staat de output op de band.

Je kunt dit beschouwen als de invoer en uitvoer van een algoritme.

Alle informatie kun je namelijk schrijven in de vorm van enen en nullen. De universele Turingmachine kan dus allerlei soorten input en output leveren.

Je weet dat de toestand waarin de eindige automaat zich bevindt, bepaald wordt door de informatie op de band én de vorige toestand van de automaat.

Informatie op de band kan dus ook een instructie zijn die door de eindige automaat wordt uitgevoerd. Op de band kun je dus niet alleen input zetten, maar ook instructies.

algoritme programmeren

Je zet de input voor het algoritme en de stappen van het algoritme in de vorm van instructies op de band.

Belangrijk voor de informatica

Het helpt informatici om te bewijzen dat een bepaald algoritme echt door een computer uit te voeren is. Het is ook een hulpmiddel om programmeertalen met elkaar te vergelijken. Als de code van twee verschillende programmeertalen door een universele Turingmachine kan worden uitgevoerd, dan noemen we die talen Turing-compleet. Je weet dan zeker dat een algoritme dat in de ene programmeertaal is geschreven, ook in de andere taal kan worden opgeschreven

Reguliere expressies

werking Alan Turing machine