Induktive Turing-maskiner

I dagens afsnit af Numb3rs taler Charlie om induktive Turing-maskiner.

Charley (to Amita): I haven’t seen an inductive Turing machine used like that before.
Amita: I’m trying to find the finite state machine for these. (points to screen)

Hvad mente de dog med det?

Turing-maskinen er et centralt begreb i teorien for algoritmer. En algoritme er en veldefineret opskrift, der kan udføres af en maskine. Algoritmen får et input og udførelsen slutter altid med et resultat. De bedst kendte eksempler på algoritmer er computerprogrammer, der som bekendt kan udføres af en computer. Også de metoder til addition, subtraktion m.v., som man lærer i skolen, er eksempler på algoritmer.

Allerede i 1930’erne begyndte matematikere at interessere sig for, hvordan man kan lave en matematisk teori for algoritmer, og denne indsats blev startskud til dét, vi i dag kender som datalogi.

Turing-maskinen er en berømt matematisk model for algoritmer; den blev oprindelig defineret af den engelske matematiker Alan Turing.

På billedet ovenfor kan man se, hvordan en Turing-maskine ser ud. Maskinen består af et bånd med uendeligt mange felter og et læsehoved, der peger på et felt på båndet. På hvert felt kan der stå enten et symbol eller ingen ting, og maskinen kan være i én af endeligt mange tilstande. En af disse tilstande er den såkaldte standsetilstand. Hvert skridt af en beregning består i, at læsehovedet bevæger sig et felt mod venstre eller mod højre og skrive et symbol på det felt, det forlader, alt efter hvad det ser og alt efter hvilken tilstand, maskinen er i. En såkaldt overføringsfunktion bestemmer, hvad læsehovedet gør. Maskinens beregning standser, hvis den på et tidspunkt når standsetilstanden. Beregningens resultat er den streng af symboler, der står på båndet, når maskinen standser.

Bemærk, at en Turing-maskine ikke behøver at standse, når man giver den et input. Et simpelt eksempel er dén maskine der, uanset hvad den læser, flytter hovedet et skridt mod højre og bliver i samme tilstand.

Det første vigtige resultat om Turing-maskiner skyldes Turing selv; denne sætning, der som regel bliver omtalt som standseproblemets uafgørbarhed, siger, at der ikke findes nogen algoritme, der for en vilkårlig Turing-maskine M og et vilkårligt input w korrekt kan fortælle, om M standser på w.

Church-Turing-tesen (efter Turing og hans kollega, den amerikanske filosof og logiker Alonzo Church) er den påstand, at enhver algoritme kan udføres af en Turing-maskine. Church-Turing-tesen er ikke en matematisk sætning, for den udtaler sig om, hvordan et upræcist begreb (algoritme) kan beskrives dækkende af et matematisk veldefineret begreb (Turing-maskine).

Church-Turing-tesen kan derfor ikke bevises. Men den kan derimod modbevises. Hvis man nemlig kan finde en algoritme, der ikke kan udføres af nogen Turing-maskine, kan Church-Turing-tesen ikke være korrekt.

Mit bud på, hvad en induktiv Turing-maskine er, tager udgangspunkt i teorien om superrekursive algoritmer. Superrekursive algoritmer er matematiske modeller, der er rigere end Turing-maskinen.

Induktiv Turing-maskiner er en sådan superrekursiv model. Induktive-Turing-maskiner blev indført af den ukrainske matematiker Mark Burgin, der i dag er professor på UCLA. Denne type maskiner skal fange den naturlige observation, at man godt kan have interessante algoritmer, der aldrig standser. Et godt eksempel er en algoritme, der kan finde rødder i et polynomium med vilkårligt stor præcision. Hver iteration af algoritmen giver os en ny decimal og dermed et nyt, ændret resultat. Et andet godt eksempel er et operativsystem som Unix, Linux, OS X eller Windows – operativsystemer er i sagens natur programmer, der skal køre på computeren til evig tid uden at standse med et resultat.

En induktiv Turing-maskine er simpelthen en maskine, der kan levere et resultat uden at standse. Resultatet skal opfattes som midlertidigt; senere i beregningen kan svaret revideres.

Induktive Turing-maskiner er stærkere end sædvanlige Turing-maskiner, netop fordi der ikke er nogen betingelse om standsning. F.eks. kan en induktiv Turing-maskine levere en løsning til standseproblemet!

Den induktive Turing-maskine S skal undersøge om en givet maskine M standser på input w. S gør dette ved at have resultatet “nej” på båndet fra start; herefter begynder S at simulere hvad M gør, når M får input w. Hvis M nogen sinde standser, reviderer S sit svar til “ja”.

Eksistensen af induktive Turing-maskiner leverer ikke noget modeksempel på Church-Turing-tesen, for antagelserne om hvad en algoritme må, er anderledes end de antagelser, der ligger bag Church-Turing-tesen.