The Church-Turing-oppgaven refererer til konseptet om en effektiv, systematisk eller mekanisk metode innen logikk, matematikk og informatikk. Den er formulert som en beskrivelse av det intuitive begrepet beregnbarhet og kalles i forhold til generelle rekursive funksjoner oftere Kirkens avhandling. Det refererer også til teorien om datamaskinberegnbare funksjoner. Oppgaven dukket opp på 1930-tallet, da selve datamaskinene ennå ikke eksisterte. Den ble senere oppk alt etter den amerikanske matematikeren Alonso Church og hans britiske kollega Alan Turing.
Effektivitet av metoden for å oppnå resultatet
Den første enheten som lignet en moderne datamaskin var Bombie, en maskin laget av den engelske matematikeren Alan Turing. Den ble brukt til å tyde tyske meldinger under andre verdenskrig. Men for sin avhandling og formalisering av begrepet en algoritme, brukte han abstrakte maskiner, senere k alt Turing-maskiner. Avhandling presentererinteresse for både matematikere og programmerere, siden denne ideen inspirerte skaperne av de første datamaskinene.
I beregningsbarhetsteori er Church-Turing-avhandlingen også kjent som antagelsen om beregnbare funksjoners natur. Den sier at for enhver algoritmisk beregnelig funksjon på naturlige tall, er det en Turing-maskin som er i stand til å beregne den. Eller, med andre ord, det er en algoritme som passer for det. Et velkjent eksempel på effektiviteten til denne metoden er sannhetstabelltesten for å teste tautologi.
En måte å oppnå et ønsket resultat på kalles "effektiv", "systematisk" eller "mekanisk" hvis:
- Metoden er spesifisert i form av et begrenset antall eksakte instruksjoner, hver instruksjon uttrykkes med et begrenset antall tegn.
- Den vil kjøre uten feil, vil gi ønsket resultat i et visst antall trinn.
- Metoden kan utføres av et menneske uten hjelp med annet utstyr enn papir og blyant
- Det krever ikke forståelse, intuisjon eller oppfinnsomhet fra personen som utfører handlingen
Tidligere i matematikk ble det uformelle begrepet "effektivt beregnelig" brukt for å referere til funksjoner som kan beregnes med blyant og papir. Men selve forestillingen om algoritmisk beregningsevne var mer intuitiv enn noe konkret. Nå ble den preget av en funksjon med et naturlig argument, som det finnes en beregningsalgoritme for. En av prestasjonene til Alan Turing varrepresentasjon av et formelt eksakt predikat, ved hjelp av hvilket det ville være mulig å erstatte det uformelle, dersom metodeeffektivitetsbetingelsen brukes. Church gjorde den samme oppdagelsen.
Grunnleggende konsepter for rekursive funksjoner
Turings bytte av predikater så ved første øyekast annerledes ut enn det som ble foreslått av kollegaen. Men som et resultat viste de seg å være likeverdige, i den forstand at hver av dem velger det samme settet med matematiske funksjoner. Church-Turing-oppgaven er påstanden om at dette settet inneholder alle funksjoner hvis verdier kan oppnås ved en metode som tilfredsstiller effektivitetsbetingelsene. Det var en annen forskjell mellom de to funnene. Det var at Church bare vurderte eksempler på positive heltall, mens Turing beskrev arbeidet sitt som å dekke beregnelige funksjoner med en integral eller reell variabel.
Vanlige rekursive funksjoner
Kirkens opprinnelige formulering sier at beregningen kan gjøres ved hjelp av λ-kalkulen. Dette tilsvarer å bruke generiske rekursive funksjoner. Church-Turing-oppgaven dekker flere typer beregninger enn først antatt. For eksempel knyttet til mobilautomater, kombinatorer, registreringsmaskiner og substitusjonssystemer. I 1933 skapte matematikerne Kurt Gödel og Jacques Herbrand en formell definisjon av en klasse k alt generelle rekursive funksjoner. Den bruker funksjoner der mer enn ett argument er mulig.
Opprette en metodeλ-calculus
I 1936 opprettet Alonso Church en bestemmelsesmetode k alt λ-kalkulus. Han ble assosiert med naturlige tall. Innenfor λ-regningen bestemte forskeren deres koding. Som et resultat kalles de kirkenummer. En funksjon basert på naturlige tall ble k alt λ-beregnbar. Det var en annen definisjon. Funksjonen fra Kirkens oppgave kalles λ-beregnbar under to forhold. Den første hørtes slik ut: hvis den ble beregnet på kirkelige elementer, og den andre betingelsen var muligheten for å bli representert av et medlem av λ-kalkulen.
Også i 1936, før han studerte sin kollegas arbeid, skapte Turing en teoretisk modell for de abstrakte maskinene som nå er oppk alt etter ham. De kunne utføre beregninger ved å manipulere tegnene på båndet. Dette gjelder også andre matematiske aktiviteter som finnes i teoretisk informatikk, for eksempel kvantesannsynlighetsregning. Funksjonen fra Churchs avhandling ble først senere underbygget ved hjelp av en Turing-maskin. Til å begynne med stolte de på λ-calculus.
Funksjonsberegning
Når naturlige tall er riktig kodet som tegnsekvenser, sies en funksjon på naturlige tall å være Turing-beregnbar hvis den abstrakte maskinen fant den nødvendige algoritmen og skrev ut denne funksjonen på bånd. En slik enhet, som ikke fantes på 1930-tallet, ville i fremtiden bli ansett som en datamaskin. Den abstrakte Turing-maskinen og Churchs avhandling innledet en æra med utviklingdataenheter. Det ble bevist at funksjonsklassene formelt definert av begge forskerne faller sammen. Derfor ble begge utsagnene kombinert til ett. Beregningsfunksjoner og Churchs avhandling hadde også en sterk innflytelse på begrepet beregnebarhet. De ble også et viktig verktøy for matematisk logikk og bevisteori.
Begrunnelse og problemer med metoden
Det er motstridende syn på oppgaven. Tallrike bevis ble samlet for "arbeidshypotesen" foreslått av Church og Turing i 1936. Men alle kjente metoder eller operasjoner for å oppdage nye effektivt beregnbare funksjoner fra gitte var forbundet med metoder for å bygge maskiner, som ikke eksisterte da. For å bevise Church-Turing-tesen, tar man utgangspunkt i det faktum at enhver realistisk beregningsmodell er ekvivalent.
På grunn av mangfoldet av ulike analyser anses dette generelt for å være spesielt sterke bevis. Alle forsøk på å mer presist definere den intuitive forestillingen om en effektivt beregningsbar funksjon viste seg å være likeverdige. Hver analyse som er foreslått har vist seg å skille ut samme klasse funksjoner, nemlig de som kan beregnes av Turing-maskiner. Men noen beregningsmodeller viste seg å være mer effektive når det gjelder tid og minnebruk for forskjellige oppgaver. Senere ble det bemerket at de grunnleggende begrepene om rekursive funksjoner og Kirkens avhandling er ganske hypotetiske.
Thesis M
Det er viktig å skille mellom Turings avhandling og påstanden om at alt som kan beregnes av en dataenhet kan beregnes av maskinen. Det andre alternativet har sin egen definisjon. Gandhi kaller den andre setningen "Thesis M". Det går slik: "Alt som kan beregnes av en enhet, kan beregnes av en Turing-maskin." I oppgavens snever forstand er det en empirisk påstand hvis sannhetsverdi er ukjent. Turings oppgave og "Thesis M" er noen ganger forvirret. Den andre versjonen er stort sett feil. Ulike betingede maskiner er beskrevet som kan beregne funksjoner som ikke er Turing-beregnbare. Det er viktig å merke seg at den første oppgaven ikke innebærer den andre, men er i samsvar med dens falskhet.
Omvendt implikasjon av avhandlingen
I beregnelighetsteori brukes Churchs avhandling som en beskrivelse av forestillingen om beregnbarhet av en klasse av generelle rekursive funksjoner. Amerikaneren Stephen Kleene ga en mer generell formulering. Han k alte delvis rekursive alle delfunksjoner som kan beregnes av algoritmer.
Omvendt implikasjon blir ofte referert til som Kirkens omvendte avhandling. Det ligger i det faktum at hver rekursiv funksjon av positive heltall blir effektivt evaluert. I snever forstand betegner en avhandling ganske enkelt en slik mulighet. Og i bredere forstand abstraherer den fra spørsmålet om denne betingede maskinen kan eksistere i den.
Quantum-datamaskiner
Begrepene beregnerbare funksjoner og Kirkens avhandling ble en viktig oppdagelse for matematikk, maskinteori og mange andre vitenskaper. Men teknologien har endret seg mye og fortsetter å bli bedre. Det antas at kvantedatamaskiner kan utføre mange vanlige oppgaver med mindre tid enn moderne. Men spørsmål gjenstår, som stoppproblemet. En kvantedatamaskin kan ikke svare på det. Og ifølge Church-Turing-avhandlingen, ingen annen dataenhet heller.
