lørdag 3. januar 2015

Alan Turing - The Enigma

Alan Turing i 1951
(Foto: Public Domain)
Andrew Hodges' definitive Turing-biografi "Alan Turing - The Enigma" kom ut i 1983 og vart revidert i 1992. Filmen "The Imitation Game" byggjer på biografien. Andrew Hodges er sjølv matematikar og har undervist ved Wadham College, Oxford University, sidan 1986. Biografien er omfattande og imponerande, og det trass i at det har vore vanskeleg å få tak i informasjon om Alan Turing.

Upper Middle Class
Alan Mathison Turing vart fødd i 1912 av foreldre som tilhøyrde "upper middle class". Særleg mora var oppteken av plasseringa, og passa heile tida på at Alan skulle kle seg og oppføra slik at han ikkje vart teken for "lower middle class" - utan særleg hell! Faren arbeida i India, i det som heitte Indian Civil Service (ICS), og Alan vart unnfanga i India, men fødd i England. Alan hadde ein eldre bror, John.

Kostskulen Sherborne
Han gjekk på skule først på offentlege St. Michael's og seinare den private kostskulen Sherborne School. Her hadde han ei tøff tid, sær og utanfor som han var. Engelske kostskular var ikkje spesielt opptekne av kunnskapsdelen av utdanninga, men å gjera "boys to men" - å læra dei det sosiale hierarkiet og passa på at dei innordna seg det. Den konservative innstillinga gjaldt i heile samfunnet, både innan utdanning og seinare skulle han få oppleva det i militæret. Alan var mykje for seg sjølv, men fekk ein god venn i Christopher Morcom. Dessverre døydde Christopher av tuberkulose berre 18 år gammal. Det gjekk sterkt inn på Alan.

Bok og kjemisett avgjerande
Av ting som prega Alan sterkt i oppveksten, var eit kjemisett han fekk, og boka Natural Wonders Every Child Should Know (av amerikanske E. T. Brewster). Med kjemisettet gjorde han mange forsøk, ofte med det resultatet at han ikkje såg ut etterpå. Boka Natural Wonders var, ulikt engelske bøker, ei bok som gjekk rett på sak og stilte spørsmål om kven menneska eigentleg var, og kvar me kom frå. Boka fekk han som 10-åring. Alan Turing sa seinare at det var boka som opna augene hans for vitskapen, og lærte han å stilla spørsmål ved nær sagt alt.

King's College, Cambridge
(Foto: Christian Richardt)
King's College
Frå 1931 til 1934 studerte Alan ved King's College i Cambridge. Trinity College var det mest prestisjefylte innan matematikk, men miljøet ved King's var truleg betre for ein type som AT. Han leverte ei oppgåve om "the central limit theorem" og vart teken opp som Fellow at King's College, berre 22 år. Typisk nok hadde Alan bevist teoremet utan å vera klar over at det var gjort tidlegare. Det var noko som gjentok seg ofte; han sette seg ned for å løysa eit problem og såg verken til høgre eller venstre, men gjekk rett på.

"Pretty normal bisexual man"
Mykje har vore skrive og sagt om Alan Turings homoseksualitet. Men ved King's College var ikkje det noko som skapte hysteri, som elles i samfunnet. Som det heitte om ein person: "He was a pretty normal bisexual man". Det viser også den uhyre viktige verdien av den frie forsking og det frie forskings- og utdanningsmiljøet - noko å tenkja på i desse stadig meir styrte FoU-tider..

Alan Turing var open om seksualiteten sin, så open som det går an i 1930-åra i England. Han skamma seg aldri over det, slik dei fleste nok gjorde. For han var det heilt naturleg, og han forstod ikkje motviljen mot homoseksuelle og homoseksualitet. I den grad han var plaga av det, var det meir dei praktiske sidene og at han ikkje kunne leva ut homoseksualiteten fullt ut. Det vart for alvor klart i 1952..

"On Computable Numbers" og universell maskin
I 1936 leverte han arbeidet "On Computable Numbers, with an Application to the Entscheidungsproblem", der han omformulerte Kurt Gödel's artimetikk-baserte språk til ei enkel og hypotetisk maskin han kalla Universal Machine, som seinare har vorte kalla Turing Machine. I arbeidet med å motbevisa David Hilbert's påstand (Entsheidungsproblem) hadde AT "konstruert" den moderne datamaskina. Ei Turing-maskin er i stand til å utføra alt som let seg formulera som ein algoritme. Etter å ha vist kva datamaskiner (og matematikken) ikkje kan, arbeidde Turing ironisk nok resten av livet med å visa kva datamaskiner er i stand til!

Alan Turing hadde ei sjeldan gåve ved at han i tillegg til formidable abstrakte matematiske evner også var i stand til å setja dei ut i livet, som ein praktiserande ingeniør. I England hadde ikkje ingeniørar særleg statur (har dei det i dag?), i motsetnad til Tyskland og Frankrike. Det var difor ikkje vanleg å kunna kombinera teoretiske og praktiske evner. Det var noko AT fekk stor bruk for under krigen.

Laga sin eigen binære kalkulator
Men først praktiserte han det gjennom å konstruera sin eigen elektro-mekaniske binære kalkulator. Det ga han uvurderleg innsikt i samanhengen mellom det teoretiske og det praktisk fungerande. I tida 1936-38 var han mykje ved Princeton University, som då hadde vorte eit kraftsenter innan matematikk, på kostnad av Göttingen. Det var nazi-regimet å takka for det, for mange av dei mest lovande matematikarane i Tyskland og Østerrike flykta til USA og vart plukka opp av Princeton. Der var John von Neumann ein leiande figur. Men AT studerte med Alonzo Church, som like før ATs "On Computable Numbers" publiserte si eiga løysing på det same problemet (men mindre intuitivt og elegant enn AT).

Enigma-maskin (Foto: Karsten Sperling)
Enigma
Etter at England og Frankrike erklærte krig mot Tyskland i september 1939, etter den tyske invasjonen av Polen, vart Alan Turing og andre matematikarar ("men of professor type", som leiaren av GC&CS, Denniston kalla dei) kalla inn til teneste ved Government Code and Cypher School (GC and CS). GC&CS låg under marinen og var ansvarleg for kryptoanalyse. Dette var eit forsømt felt og England låg sørgjeleg langt etter. I realiteten hadde det ikkje skjedd stort sidan første verdskrigen. Men engelskmennene var heldige og fekk god starthjelp frå polakkane, som hadde klart å identifisera vesentlege detaljar om tyskarane sine Enigma-maskiner.

Tyskland baserte nesten all kommunikasjon på krypterte meldingar frå Enigma-maskiner. Dette var militært forbetra utgåver av den kommersielt tilgjengelege Enigma. Den militære utgåva hadde eit pluggbord kopla til, noko som auka talet på mulege kombinasjonar vesentleg. Talet på mulege kombinasjonar var så høgt (1,3 x 10**12 for kvar av dei 6 x 17 656 rotor-posisjonane) at det vart sett på som heilt umuleg å knekkja. Og med eit reint "brute force"-angrep utan noko førehandskunnskap, ville oppgåva vera umuleg.

Polen langt framme på kryptoanalyse
Men polakkane hadde fått tak i koplingsoppsettet til rotorane (the wiring of the rotors) via fransk etterretning. Også engelskmennene hadde fått denne informasjonen, men utan å føreta seg noko. Polakkane sette imidlertid tre topp-matematikarar på saka og klarte å avsløra koplingane. Det essensielle med Enigma-maskinene var oppsettet (rotorinnstillinga) for kvar gang. Denne vart skifta kvart døgn, kl. 24.00 presist. Det var dette oppsettet som var heilt vesentleg å finna ut av, for å kunna dekryptera meldingane det følgjande døgnet. Og tida var heilt avgjerande; det hjelpte lite å finna rotorposisjonane dagen etter. Polakkane bygde ei elektromekanisk maskin (= "a Bombe") for å køyra eit "brute force"-angrep på alle mulege rotorposisjonar gitt at dei visste ein bokstavsekvens. Men hausten 1938 endra tyskarane Engima-maskinene sine og sette inn fleire rotorar, og dermed måtte polakkane gi opp.

Fungerande kopi av ei Turing-bombe
(Foto: Tom Yates)
Meir avanserte "bomber"
Slik var situasjon då Alan Turing & co. overtok. Dei fann til slutt fram til ei langt meir avansert "bombe" (namnet fekk maskinene fordi dei ga ein tikkande lyd etter kvart som dei leitte seg fram gjennom rotorposisjoanr). AT var sentral i dette arbeidet, men også kollegaen hans Gordon Welchman kom med avgjerande løysingsforslag slik at det til saman vart ei genial maskin. Den første prototypen var klar i mai 1940 og etter kvart vart fleire laga. Dei var ikkje plasserte ved Bletchley, men på ulike stasjonar utanfor, der dei vart passa på av damer ved Women's Royal Navy Service (WRENS) som fortløpande las av posisjonar gitt av maskinene. Desse posisjonane vart så sende tilbake til Bletchley. Dei som arbeida med maskinene visste ikkje kva dei dei var med på, dei gjorde berre som dei fekk fortalt. Det var eit spesielt miljø ved desse stasjonane:
They were impressive and rather beautiful machines, making a noise like that of a thousand knittting needles as the relay switches clicked their way through the proliferating implications.
Kryptoanalyse meir enn "brute force"
Sjølv om desse maskinene på sett og vis utførte brute force"-angrep, handlar kryptoanalyse om langt meir enn å prøva ut alle mulege kombinasjonar. Dei ville ikkje hatt ein sjanse til å løysa krypteringane om dei ikkje visste noko på førehand. Tyskarane på si side hadde så stor tiltru til Enigma at dei ikkje fann grunn til å undersøkja nærmare om krypteringane kunne vore brotne, sjølv når dei hadde gode grunnar til å mistenkja det. Kanskje var det den tyske ingeniør-mentaliteten som gjorde seg gjeldande, der dei la all skjebnen i maskinene sine. Men det som var kryptert med maskiner kunne også dekrypterast ved hjelp av maskiner. Faktisk var ikkje Enigma og kryptomaskiner nødvendigvis sikrare enn gammaldags handkryptering:
Machine ciphers were not inherently secure, as the Enigma proved. The Foreign Office continued to use a hand system based on books; it remained unbroken. Blethcley deciphered the Italian's naval mchine system; but was increasingly powerless against their book ciphers. What was enciphered on a machine might all the easier be deciphered on a machine.
Churchill forstod
Churchill sjølv besøkte Bletchley Park hausten 1941 og var imponert av det han såg. Han skjønte, i motsetnad til store delar av marinen, kor viktig dette arbeidet var, og ba om å få dagleg oppdatering av arbeidet og viktige tyske meldingar. Han kalla Bletchley-miljøet for "the geese that laid the golden eggs and never cackled".

Nokre veker seinare skreiv Alan Turing og tre av kollegaene hans eit brev direkte til Churchill der dei forklarte problema med underbemanning og at dei difor ikkje klarte å halda tritt med nødvendig dekryptering. Churchill ga umiddelbart ordre vidare: "Make sure they have all they want on extreme priority and report to me that this has been done!". Nødvendige ressursar, både i form av arbeidskraft til å lesa av "bombene" og ressursar elles, kom på plass og dei var i stand til å halda tritt med den store mengda tyske meldingar.

Det var altså slett ikkje slik det vart framstilt i "The Imitation Game" at Turing åleine skreiv brev til Churchill og at det var for å finansiera den første "bomba".

Systematisert sannsynlegheitsrekning
Ein annan stor feil i filmen er sekvensen om Alan Turing som utviklar eit system for sannsynlegheitsrekning til bruk for å avgjera kva dekrypterte meldingar som skal sendast vidare eller forkastast. Det er ei heilt feil framstilling av historia. Alan Turing utvikla ein matematisk teori basert på Bayesisk sannsynlegheitsrekning for å få ei betre og meir systematisk gjetting av cipher-tekst slik at det kunne gjerast maskinelt. Dette arbeidet var sentralt i å vidareutvikla dekrypteringa og halda tritt med meldingane til den tyske marinen.

Kryptert tale
Mot slutten av 1943 hadde krigen teke ei vending og dei allierte fått eit bra overtak. Det var ikkje like stort behov for ATs tenester og han begynte å interessera seg for nye problem: kryptering og dekryptering av tale. Han gjorde banebrytande arbeid her ved Hanslope Park, som han etter kvart flytta til. Men ikkje noko av dette arbeidet vart brukt i krigen.

For innsatsen under krigen mottok Alan Turing utnemninga Order of the British Empire (OBE).

ACE - den første universelle maskina
Etter krigen vart Alan Turing knytt til utviklinga av ACE (Automatic Computing Engine) ved National Physical Laboratory (NPL). Alan argumenterte sterkt for bygging av ei universell datamaskin som han hadde vist prinsippet for i 1936-paperet. Men det var ikkje mange som forstod idéane hans, og han var ikkje akkurat ein meistar i kommunikasjon heller. For AT var det viktig å skilja instruksjonar frå maskinvare, og gjera den siste så generell (universell) og enkel som muleg. Men i siste halvdel av 1940-talet tenkte dei fleste på datamaskiner som avanserte kalkulatorar, og ville byggja inn så mykje funksjonalitet som muleg direkte i maskinvara.

Mark I ved Manchester University
Det vart mykje konfliktar og Alan Turing hoppa etter kvart av og gjekk tilbake til King's. Etter ei stund fekk han tilbod om å bli med på det konkurrerande prosjektet Mark I vec Manchester University. Planane for denne maskina gjekk ikkje så langt som ACE, og den var meir spesialisert. Alan skreiv Programmers' Handbook som dokumentasjon på bruken, men du skulle ha eit ganske godt innblikk i maskina om du skulle forstå det som stod der. Turing brydde seg heller ikkje om å oversetja base-32 til meir forståelege teikn; han "snakka" flytande base-32 og såg ikkje kva som var problemet.

Bruken av datamaskina var ikkje lett:
[Using the machine].. required considerable physical stamina. Starting in the machine room you alerted the engineer and then used the hand swithces to bring down and enter the input program. A bright band on the monitor tube indicated that the waiting loop had been entered. When this had been achieved, you ran upstairs and put the tape in the tape reader and then returned to the machine room. If the machine was still obeying the input loop you called to the engineer to switch on the writing current, and cleared the accumulator (allowing the control to emerge from the loop). With luck, the tape was read. As soon as the pattern on the monitor showed that input was ended the engineer switched off the write currendt to the drum. Programs which wrote to the drum during the execution phase were considered very daring. As every vehicle that drove past was a potential source of spurious digits, it usually took many attempts to get a tape in - each attempt needing another trip up to the tape room.
"Missed opportunity"
Turing hadde omtalt alt som utgjer eit program, men det som mangla var å skriva det ut i samanheng. Han hadde mentalt klart for seg kva eit programmeringsspråk var. Han hadde alt som skulle til for å formulera det og definera feltet; både abstrakt matematisk kunnskap og teknisk innsikt i korleis datamaskiner fungerte. Han kunne ha skapt det første programmeringsspråket, men det var ei mulegheit han enten droppa eller ikkje heilt såg nødvendig.

Fellow of the Royal Society
I 1951 vart han utnemnt til Fellow of the Royal Society (FRS), ei stor ære. Sir Geoffry Jefferson, sjølv FRS frå 1947, og ein av dei som hadde gått sterkast mot Alans syn på den elektronisk hjernen og datamaskiner som i framtida ville kunna imitera menneske, sende denne gratulasjonen, med eit vennleg lite spark:
I am so glad; and I sincerely trust that all your valves are glowing with satisfaction, and signalling messages that seem to you to mean pleasure and pride! (but don't be decieved!)

Alan Turing sa sjølv om FRS-utnemninga: I hope I am not described as "distinguished for work on unsolvable problems".

Kunstig intelligens
Alan Turing var heile livet oppteken av forholdet mellom hjerne (mind) og maskin. Han hadde stor tru på at maskinene ein dag ville kopiera menneska, og at sidan han meinte at hjernen opererte som ei "discrete state"-maskin, ville det vera muleg å emulera den.

Rettsak og kjemo-terapi
I 1952 skjedde det fatale då det først var eit innbrot i Alan Turing si leilegheit. Men då politiet vart trekt inn, interesserte dei seg meir for Alan Turing sin legning enn for innbrotet, og det enda med tiltale og straffesak fordi han hadde hatt seksuell omgang med menn, noko han ikkje la skjul på. Han vart dømd og fekk valet mellom fengsel i to år eller kjemo-terapi i eitt år (medisinering med østrogen). Han valde det siste, og gjekk på østrogenbehandling i eitt år. Verre var det at han ikkje kunne praktisera seksuelt i England, og han reiste difor utanlands, mellom anna til Norge. I Bergen fekk han ein venn som heitte Kjell (eller vart kalla Kjell).

Då behandlinga var over fekk Alan etter kvart eit tilbod om bortimot fast stilling ved Manchester University. Det var i første omgang for fem år, men som kunne forlengjast til 10 år. Stillinga heitte Readership in the Theory of Computing og han var i praksis fri til å gjera det han ville, når han ville og kor han ville.

Plakett utanfor Turing sitt hus i Wilmslow,
Cheshire (Foto: Joseph Birr-Pixton)
Overraskande sjølvmord
Sjølvmordet den 7. juni 1954 kom difor svært overraskande på alle. Det var meir enn to år sidan rettsaka og meir enn eitt år sidan han avslutta østrogenbehandlinga. Han hadde fått fast jobb med universitetet i Manchester og var fri til å gjera det han ville. Det var slik sett veldig rart at han skulle velja å avslutta livet på det stadiet, sjølv om han sikkert hadde problem nok. Den vanlege myten er at han tok livet i samband med østrogenbehandlinga, men det er vanskeleg å slå fast nokon klar samanheng.

Det er også vanleg å hevda at han døydde av cyanidforgifting etter å ha ete av eit forgifta eple, akkurat som Snøkvit. Det vart fastslege at dødsårsaka var cyanidforgifting, men eplet vart aldri undersøkt! Det er difor ikkje fastslege 100 % at dette var dødsårsaka, sjølv om mykje peikar i den retninga.

Mora godtok aldri at Alan Turing tok sitt eige liv og meinte at det heller hadde skjedd som følgje av ei ulykke. Andre har seinare kopla dødsfallet til Alan Turings ustabilitet og den sikkerheitsrisikoen han truleg vart oppfatta å vera. Men saka vart aldri etterforska, sjølv om fleire har teke til orde for at saka burde takast opp att, i det minste for å utelukka at hendinga hadde noko med hemmelege tenester å gjera.

Offentleg orsaking
Så seint som 24.12.2013 signerte dronning Elisabeth II ein offentleg "pardon", og den vart først offentleg annonsert i august 2014. Då hadde mange arbeida lenge for å få reinvaska Alan Turing og få ei offentleg orsaking. Ein offentleg "pardon" er
".. the forgiveness of a crime and the cancellation of the relevant penalty; it is usually granted by a head of state (such as a monarch or president) or by acts of a parliament or a religious authority." 
Denne typen orsaking og frikjenning er sjeldan, men så er Alan Turing si sak også spesiell.





7 kommentarer:

Lars Marius Garshol sa...
Denne kommentaren har blitt fjernet av forfatteren.
Lars Marius Garshol sa...

Veldig bra oppsummering! Godt gjort å få med så mye på så lite plass.

Merk at paperet fra 1936 ikke er basert på Gödels arbeid. Hilberts program inneholdt tre grunnleggende metamatematiske teser som skulle bevises. Gödel knuste programmet ved å motbevise den første tesen (alle sanne setninger kan utledes i et formelt system). Det var et hardt slag for Hilbert, som han hadde vansker med å akseptere.

Det Turing gjorde var å motbevise tese nummer to (alle matematiske spørsmål har en algoritme som kan besvare spørsmålet). Så det er en sammenheng mellom arbeidene, men Turing bygde ikke på noen måte videre på Gödels arbeid.

(Måtte legge til kommentaren på nytt. Det manglet en helt sentral "ikke".)

Svein Ø sa...

Takk for det. I boka blir Gödel kreditert med å ha tilbakevist Hilberts første og andre påstand, om completeness og consistence. Den tredje utfordringa frå Hilbert var Entscheidungs-problemet (decision problem), difor var også den fulle tittelen på paperet "On Computable Numbres with an application to the Entscheidungsproblem".

Og Entscheidungsproblemet er som du skriv, eit spørsmål om det finst algoritmar som kan gi eit klart ja- eller nei-svar på eit spørsmål av første ordens logikk. Turing viste med si universelle maskin at det finst matematiske spørsmål som ikkje kunne løysast med algoritmar. Cantors "diagonale argument" var ein sentral del av beviset.

Lars Marius Garshol sa...

Du har rett: jeg husket feil. Gödel tok både nr 1 og 2 i én smell. Men Turing sitt paper er altså om et annet problem enn det Gödel løste. (Det viste seg å egentlig bare være ett problem, fordi det viser seg at i praksis må du velge mellom completeness eller consistence.)

Men det er ikke rett at paperet til Turing brukte diagonal-argumentet til Cantor. Cantor brukte det første gang for å vise at det er flere desimaltall enn heltall, selv om det er uendelig mange av begge to. Selve argumentet er meget elegant, og var faktisk en helt ny bevisteknikk. (Akkurat det er noe man ikke ser så ofte.) Man stiller opp to uendelige mengder i en matrise, og viser så at ved å systematisk modifisere elementene langs diagonalen kan man få et nytt element som ikke finnes i den ene av de to mengdene.

Turings bevis var konstruert på en helt annen måte, med tradisjonell reductio ad absurdum. Som forsåvidt Gödel også brukte, i en litt annen form.

Turings bevis er faktisk ganske enkelt å forstå. (Cantors likeså. Gödels, derimot, ...) For å motbevise Hilberts påstand trenger man et problem som ingen Turing-maskin kan svare ja/nei på.

Turings forslag var stoppe-problemet: dvs, kan vi svare på om en Turing-maskin vil stoppe eller ikke på en gitt input? Dette kan virke nokså enkelt, men hvordan skal det fungere? Sett at Turing-maskinen tar ingen input, og setter i gang med å lete etter en løsning på, si, Fermats siste sats. Dersom den finner en løsning stopper den og skriver den ut, hvis ikke, stopper den ikke. Hvis du kan lage en Turing-maskin som kan løse stoppe-problemet ville vi altså ikke trengt å vente 350 år på matematikerne, vi kunne bare lånt din Turing-maskin og stappet inn den for Fermat-problemet.

Men anta så en Turing-maskin T som kan ta som input en annen Turing-maskin A og dennes input, og så svarer på om denne maskinen (A) noen gang vil stoppe med denne inputen. Her antar vi bare at denne finnes. (Merk at det var for å sannsynliggjøre eksistensen av T at Turing trengte en universell Turing-maskin.)

Hvis T finnes kan vi lage en ny Turing-maskin, T', som tar som input en annen Turing-maskin A' og dennes input. Hvis A' stopper på denne inputen, så kjører T' i evig løkke. Hvis A' ikke stopper, så stopper T'.

Gi nå T' som input T' og T'. Nå vil T' gå i evig løkke hvis den stopper, og stoppe hvis den går i evig løkke. Det er jo umulig. Altså kan ikke T' finnes. Og heller ikke T, for hvis T finnes er det trivielt å lage T'. Altså har ikke die Entscheidungsproblem noen løsning.

Matematiske lærebøker i complexity theory går gjennom dette hvis du vil ha det mer formelt. Charles Petzolds "The Annotated Turing" gir en veldig klar og grundig presentasjon av det opprinnelige paperet, men det er mye jobb å lese gjennom hele boken. Dvs, det er ikke så vanskelig, men rett og slett mye jobb å følge alle resonnementene fordi det er så mange av dem.

Lars Marius Garshol sa...

I dag snublet jeg tilfeldigvis over dette paperet: http://arxiv.org/abs/1409.5944

I seksjon 2.1 vises Turings teorem nettopp med Cantors diagonalbevis. Så det går an!

Svein Ø sa...

Bra med alternative forklaringar, sjølv om eg må innrømma at eg ikkje heilt heng med..
Stemmer forresten setninga:

Gi nå T' som input T' og T'

Hodges tek utgangspunkt i Cantors diagonalargument når han forklarer Turings bevis. Eg prøver å gjengi forklaringa mest for å prøva å forstå den sjølv..

Cantors diagonalargument var som du skriv, ein elegant og ny måte å bevisa at det finst fleire irrasjonelle tal enn rasjonelle (irrasjonelle = tal som ikkje kan uttrykkjast som ein brøk). Han viste også at det finst færre rasjonelle tal ("brøk-tal") enn heiltal.

Lista av alle rasjonelle tal mellom 0 og 1 uttrykt med brøk:
1/2 1/3 1/4 2/3 1/5 1/6 2/5 3/4 1/7 3/5 1/8 2/7 4/5 1/9 3/7 1/10

Dei 10 første i tabellform, uttrykt i desimalform (berre dei 10 første desimalane):

,5000000000
,3333333333
,2500000000
,6666666666
,2000000000
,1666666666
,4000000000
,7500000000
,1428571428
,6000000000

Talet som kjem fram som ein diagonal i tabellen: ,5306060020 er eit irrasjonelt tal. Trikset til Cantor var å endra kvart siffer med 1 og få dette talet: ,6417171131 som umuleg kunne vera eit rasjonelt tal sidan det skil seg frå det første rasjonelle talet i lista i første siffer (og frå det 695. talet i lista på siffer 695 osv.).

Det som var relevant for Turing i dette eksempelet var at det rasjonelle ga opphav til det irrasjonelle. Eller i Turings vokabular: Computable numbers ga opphav til uncomputable numbers (jf. tittelen på artikkelen hans: "On Computable Numbers.."). Det var dette som ga han svaret på Hilberts påstand/spørsmål og overbeviste han om at svaret måtte vera 'nei'. Han viste ved hjelp av den universelle maskina eit uløyseleg problem (at det finst matematiske problem, formulert som algoritme, som det ikkje finst eit 'ja'- eller 'nei'-svar på, altså logisk uløyseleg).

Det er framleis ein god del arbeid frå det innleiande over og til sjølve beviset, men dette hovudtankegangen Hodges refererer til i boka.

Lars Marius Garshol sa...

T' og T' som input til T' stemmer faktisk, selv om jeg er enig at det ser merkelig ut. T' er en maskin som tar som input en annen maskin pluss dens input og evaluerer om denne maskinen ville stoppet på denne inputen. Det er det at vi setter T' til å sjekke seg selv som gjør at det blir et paradoks.

Jeg slo opp i Hodges og ser nå at han sier at Cantors diagonalbevis inspirerte paperet om Computable numbers. Det har han helt sikkert rett i, og da skjønner jeg hva du mener. Turing ble inspirert av Cantors diagonalbevis, selv om han ikke baserte sitt eget bevis på det.

Og når jeg slår opp i Petzold ser jeg at faktisk så er det et diagonalbevis i On Computable numbers, i seksjon 8. Men Turing skriver "by applying the diagonal process argument correctly, we can show that there cannot be any such general process. ... This proof, although perfectly sound, has the disadvantage that it may leave the reader with a feeling that 'there must be something wrong'. The proof which I shall give has not this disadvantage, and gives a certain into the significance of the idea 'circle-free'."

Det hadde jeg helt glemt, at det faktisk er et diagonalbevis i paperet også.

Rett etter dette, med bare et par setninger mellom, gir han en variant av det beviset jeg ga i forrige kommentar. I seksjon 11 bruker han så det for å vise at die Entscheidungsproblem (som formulert av Hilbert) derfor ikke har noen løsning.

Så ble Turing inspirert av Cantors diagonalbevis? Det ser jo absolutt sånn ut. Baserte han sitt bevis på det? Tjah. Det spørs hvordan du definerer "baserte", men det blir vanskelig å påstå at det du skrev var helt feil.

Jaja. Jeg trodde jeg husket dette 100%. :-)