Turingmaskiner og beregningsteori

I 1936, for å beregne enhver beregningsfunksjon, oppfunnet maskinen av "Alan Turing" ble oppkalt "Turing Machine (TM)”. I informatikk er TM den abstrakte matematiske beregningsmodellen og primær teoretisk konstruksjon. Turing-maskiner jobber gjennom et forhåndsprogrammert utallig antall instruksjoner. Det spiller en viktig rolle og hjelper brukerne med å finne beregningen ved å avgrense "Beregnbare funksjoner”.

Denne oppskrivningen vil kort forklare Turing-maskiner, deres arbeids- og beregningsteori.

Hva er Turing Machine?

Turing -maskinen ble oppfunnet av Alan Turing. Opprinnelig ble den kalt en “A-maskin (automatisk maskin)”. Senere ble dette begrepet endret til “Turing Machine" av "Alonzo Church”, Som var Turings doktorgradsrådgiver.

En Turing -maskin er en matematisk beregningsmodell basert på uendelige instruksjonssett som brukes til å implementere hvilken som helst datamaskinalgoritme. Manipulering av symboler gjøres i henhold til en tabell med regler på en båndstripe.

Hvordan fungerer Turing Machine?

Turing -maskinen jobber med et uendelig minnebånd delt inn i individuelle celler. Hver celle kan holde ett symbol trukket fra et uendelig sett med symboler. Disse symbolene er kjent som maskinalfabetet. Maskinen har en "HODE”Det peker på starttilstanden for å implementere databehandlingsalgoritmen.

I tillegg kan det flyttes over en av disse cellene som skal plasseres. Utvalget av “stat”Kan gjøres fra et endelig sett med stater. Hodet leser symbolet (maskin alfabeter) fra cellen i hvert trinn. Etter å ha lest cellesymbolet, kan det nye symbolet legges til samme celle av Turing -maskinen. I bunnen av det nye symbolet kan det bevege hodepekeren ett trinn til høyre eller venstre. Det kan være mulig at beregningsprosessen stopper.

Hva er kompatibilitet og kirkes avhandling?

Kompatibilitet er ikke bare A-maskin (Turing Machine), en rekursiv funksjon, Pascal-programmeringsspråk eller kalkulus, men kombinasjonen av alle. Alonzo Church, Turings doktorgradsrådgiver, introduserte dette konseptet kjent som “Kirkens avhandling”. Det kalles også “Kirke-turing avhandling”.

Dessuten er det ikke et teorem, men brukes til å sammenligne den beregnelige funksjonen med funksjonene som kan beregnes av A-maskin. De funksjonene som ikke kan beregnes av A-maskiner, kan ikke beregnes med en annen metode. Da konseptet med kirkens avhandling ble formulert, visste folk på den tiden ikke om evnen til moderne datamaskiner, og det var en så betydelig prestasjon.

Turingmaskiner og beregningsteori

Et naturlig tallsett er et avgjørende eller Turing Computable Set. For eksempel har vi en Turing -maskin med nummeret "m”, Som blir stopper når utgangen er 1 hvis“m”Er i det beregnelige settet. På den annen side stopper det når utgangen er 0 hvis "m”Er ikke i det naturlige tallsettet. En funksjon “r”Fra et naturlig tall til et naturlig tall er et“Turing Computable”. Det kan observeres at ikke alle naturtallsett kan beregne.

Vi har forklart konseptet med Turing -maskinen og beregningsteorien.

Konklusjon

Turing -maskinen ble oppfunnet av “Alan Turing”I 1938 for å beregne enhver beregningsfunksjon. Det er den abstrakte matematiske beregningsmodellen og en sentral teoretisk konstruksjon innen informatikk. En Turing -maskin er en matematisk beregningsmodell basert på uendelige instruksjonssett som brukes til å implementere hvilken som helst datamaskinalgoritme. Manipulering av symboler gjøres i henhold til en tabell med regler på en båndstripe. Denne oppskrivningen demonstrerte begrepene Turing-maskiner og beregningsteori.