Universal Turing maskine

En Turing-maskine er en universel Turing -maskine , der kan erstatte enhver Turing-maskine. Efter at have modtaget programmet og inputdata som input, beregner den det svar, som Turing-maskinen, hvis program blev givet som input, ville beregne ud fra inputdataene.

Formel definition

Programmet for enhver deterministisk Turing-maskine kan skrives ved hjælp af et endeligt alfabet bestående af tilstandssymboler, parenteser, pile og så videre; Lad os betegne dette maskinalfabet som . Så er en universel Turing-maskine U til en klasse af maskiner med et alfabet og k inputbånd en Turing-maskine med k + 1 inputbånd og et alfabet sådan, at hvis de første k bånd gives en inputværdi, og k + 1  er givet den korrekt skrevne kode for en Turing-maskine , så vil U give det samme svar, som det ville på dette input , eller vil køre på ubestemt tid, hvis det ikke stopper ved dette input.

Den universelle Turing-maskine-sætning siger, at en sådan maskine eksisterer og modellerer andre maskiner med højst kvadratisk deceleration (dvs. hvis den originale maskine tog t skridt, så vil den universelle maskine højst tage ct² ). Beviset for denne sætning er konstruktiv (sådan en maskine er nem at bygge, du skal bare omhyggeligt beskrive den). Sætningen blev foreslået og bevist af Turing i 1947  .

Se også