Trwałe znaczenie Turinga

Kiedy 100 lat temu, 23 czerwca 1912 roku, urodził się Alan Turing, komputer nie był rzeczą – był osobą. Wynajmowano komputery, z których większość stanowiły kobiety, do wykonywania powtarzalnych obliczeń na wiele godzin. Praktyka ta sięga lat pięćdziesiątych XVIII wieku, kiedy Alexis-Claude Clairaut zwerbował dwóch kolegów astronomów, aby pomogli mu wyznaczyć orbitę komety Halleya. Podejście Clairauta polegało na podzieleniu czasu na segmenty i, korzystając z praw Newtona, obliczeniu zmian pozycji komety podczas mijania Jowisza i Saturna. Zespół pracował przez pięć miesięcy, powtarzając ten proces raz po raz, powoli wykreślając przebieg ciał niebieskich.

Dziś nazywamy ten proces dynamiczną symulacją; Współcześni Clairaut nazywali to obrzydliwością. Pragnęli nauki podstawowych praw i pięknych równań, a nie tablic i tablic liczb. Mimo to jego zespół dokładnie przewidział peryhelium komety Halleya. W ciągu następnego półtora wieku metody obliczeniowe zdominowały astronomię i inżynierię.

Ta historia była częścią naszego wydania z marca 2012

• Zobacz resztę numeru
• Subskrybuj

Zanim Turing wstąpił do King’s College w 1931 roku, ludzkie komputery były wykorzystywane do wielu różnych celów — często wspomagały je maszyny liczące. Do kontroli krosien i zestawiania wyników amerykańskiego spisu powszechnego używano kart dziurkowanych. Rozmowy telefoniczne były przełączane za pomocą numerów wybieranych na dzwonku i interpretowane przez szereg 10-stopniowych przekaźników. Kasy były wszechobecne. Milioner to nie tylko bardzo bogata osoba — to także mechaniczny kalkulator, który potrafił mnożyć i dzielić z zadziwiającą szybkością.

Wszystkie te maszyny były zasadniczo ograniczone. Były nie tylko wolniejsze, mniej niezawodne i znacznie uboższe w pamięć niż dzisiejsze komputery. Co najważniejsze, maszyny liczące i przełączające z lat trzydziestych – a także te, które zostaną wprowadzone na wiele lat – zostały zbudowane w określonym celu. Niektóre maszyny mogły wykonywać manipulacje matematyczne, inne mogły nawet wykonywać zmienną sekwencję instrukcji, ale każda maszyna miała skończony repertuar przydatnych operacji. Maszyny nie były uniwersalne. Oni nie byli programowalny.

Rzeczy zrecenzowane

• Katedra Turinga: początki cyfrowego wszechświata

  George Dyson
  Książki Panteonu, 2012

• Kiedy komputery były ludźmi

  David alan grier
  Wydawnictwo Uniwersytetu Princeton, 2005

  
  
  

• Alan Turing: Zagadka

  Andrzeja Hodgesa
  Szymon i Schuster, 1983

Tymczasem matematyka miała kłopoty.

We wczesnych latach dwudziestych wielki niemiecki matematyk David Hilbert zaproponował sformalizowanie całej matematyki za pomocą niewielkiej liczby aksjomatów i zestawu spójnych dowodów. Hilbert wyobraził sobie technikę, której można by użyć do weryfikacji dowolnych twierdzeń matematycznych — wziąć twierdzenie takie jak x + y = 3 i x – y = 3 i określić, czy jest ono prawdziwe, czy fałszywe. Ta technika nie opierałaby się na wglądzie lub inspiracji ze strony matematyka; musiał być powtarzalny, możliwy do nauczenia i na tyle prosty, aby mógł być śledzony przez komputer (w znaczeniu tego słowa Hilberta). Taki system dowodzący twierdzeń byłby rzeczywiście potężnym materiałem, ponieważ wiele aspektów świata fizycznego można z łatwością opisać jako zbiór równań. Gdyby można było zastosować powtarzalną procedurę, aby dowiedzieć się, czy zdanie matematyczne jest prawdziwe, czy fałszywe, wówczas fundamentalne prawdy dotyczące fizyki, chemii, biologii — a nawet społeczeństwa ludzkiego — byłyby możliwe do odkrycia nie poprzez eksperymenty w laboratorium, ale przez matematyków przy tablicy. .

Ale w 1931 austriacki logik Kurt Gödel przedstawił swoje niszczycielskie twierdzenie o niezupełności. Pokazał, że dla każdego użytecznego systemu matematyki możliwe jest stworzenie twierdzeń, które są prawdziwe, ale nie można ich udowodnić. Potem przyszedł Turing, który wbił ostatnią stawkę w projekt Hilberta — i tym samym wytyczył drogę ku przyszłości informatyki.

Jak pokazał Turing, problemem nie jest tylko to, że niektórych twierdzeń matematycznych nie da się udowodnić; w rzeczywistości nie można wymyślić żadnej metody, która mogłaby we wszystkich przypadkach określić, czy dane zdanie jest dowodliwe, czy nie. Oznacza to, że każde stwierdzenie na tablicy może być prawdziwe, może być fałszywe, może być niemożliwe do udowodnienia… a często nie można określić, które. Matematyka była zasadniczo ograniczona — nie ludzkim umysłem, ale samą naturą matematyki.

Genialną, zadziwiającą rzeczą był sposób, w jaki Turing podchodził do swojego dowodu. Wynalazł logiczny formalizm, który opisał, w jaki sposób ludzki komputer, nauczony wykonywania złożonego zestawu operacji matematycznych, faktycznie je przeprowadza. Turing nie rozumiał, jak działa ludzka pamięć, więc zamodelował ją jako długą taśmę, która może się poruszać w przód iw tył oraz na której można zapisywać, wymazywać i czytać symbole. Nie wiedział, jak działa ludzkie uczenie się, więc wymodelował je jako zbiór zasad, których człowiek będzie przestrzegał w zależności od symbolu, który jest przed nią i pewnego rodzaju wewnętrznego stanu umysłu. Turing opisał ten proces tak szczegółowo, że ostatecznie do jego wykonania nie był nawet potrzebny ludzki komputer — zamiast tego mogła to zrobić maszyna. Turing nazwał ten byt teoretyczny automatem lub a-maszyną; dzisiaj nazywamy to maszyną Turinga.

W artykule z 1936 roku Turing udowodnił, że a-maszyna może rozwiązać każdy problem obliczeniowy, który można opisać jako sekwencję kroków matematycznych. Co więcej, pokazał, że jedna a-maszyna może symulować inną a-maszynę. To, co dało maszynie a tę moc, to fakt, że jej taśma mogła przechowywać zarówno dane, jak i instrukcje. Według historyka nauki George’a Dysona, na taśmie znajdowały się obie liczby, które: oznaczać rzeczy i liczby, które robić rzeczy.

Dzieło Turinga było przełomowe. Wyjaśniło to projektantom wczesnych komputerów elektronicznych, że maszyny liczące nie potrzebują ogromnego spisu wymyślnych instrukcji lub operacji — wystarczyło im kilka rejestrów, które były zawsze dostępne (stan umysłu) i magazyn pamięci, który mógł pomieścić zarówno dane, jak i kod. Projektanci mogli postępować z matematyczną pewnością, że maszyny, które budowali, będą w stanie rozwiązać każdy problem, który ludzie mogliby zaprogramować.

Te spostrzeżenia dostarczyły matematycznego sformułowania dla dzisiejszych komputerów cyfrowych, chociaż to John von Neumann podjął idee Turinga i przypisuje mu się projekt maszyn. Projekt von Neumanna miał centralny rdzeń, który pobierał zarówno instrukcje, jak i dane z pamięci, wykonywał operacje matematyczne, przechowywał wyniki, a następnie powtarzał. W razie potrzeby maszyna może również sprawdzać zawartość wielu lokalizacji w pamięci. To, co teraz nazywamy architekturą von Neumanna, jest sercem każdego mikroprocesora i komputera mainframe na świecie. Jest znacznie bardziej wydajny niż a-maszyna, ale matematycznie jest taki sam.

Nawiasem mówiąc, ta istotna cecha komputerów pomaga wyjaśnić, dlaczego cyberbezpieczeństwo jest jednym z najbardziej niepokojących problemów współczesności. Po pierwsze, Turing wykazał, że wszystkie a-maszyny są sobie równoważne, co umożliwia atakującemu przejęcie komputera docelowego i uruchomienie przez niego programu wybranego przez napastnika. Ponadto, ponieważ nie zawsze można rozpoznać, co można udowodnić, maszyna Turinga nie może — bez względu na to, ile ma pamięci, prędkości lub czasu — ocenić projektu innej maszyny Turinga i niezawodnie określić, czy druga maszyna po otrzymaniu niektóre dane wejściowe, kiedykolwiek zakończą obliczenia. To uniemożliwia doskonałe wykrywanie wirusów. Program nie może ocenić wcześniej niewidzianego oprogramowania i określić, czy jest złośliwy, bez faktycznego jego uruchomienia. Program może być łagodny. Lub może działać przez lata, zanim wyczyści pliki użytkownika. Nie ma sposobu, aby wiedzieć na pewno bez uruchamiania programu.

W 1938 Turing rozpoczął współpracę z rządem brytyjskim i ostatecznie pomógł zaprojektować serię maszyn do łamania kodów używanych przez Niemców podczas II wojny światowej. Najlepszym źródłem tej historii jest biografia Andrew Hodgesa Alan Turing: Zagadka. Niestety, niektóre szczegóły dotyczące wojennej pracy Turinga nie zostały odtajnione aż do 2000 roku, 17 lat po książce Hodgesa (i prawie 50 lat po samobójstwie Turinga). W rezultacie jego pełny wkład nie został dobrze opowiedziany.

Wiele historii informatyki sprawia wrażenie, że użycie kart perforowanych, następnie przekaźników, lamp i wreszcie tranzystorów do budowy maszyn obliczeniowych było prostym zbiorem decyzji inżynierskich. Ale tak nie było. Maszyny ogólnego przeznaczenia wymagały fundamentalnej wiedzy Turinga, że ​​dane i kod mogą być reprezentowane w ten sam sposób. I pamiętaj, że wszystkie dzisiejsze komputery zostały opracowane przy pomocy wolniejszych komputerów, które z kolei zostały zaprojektowane z wolniejszymi komputerami. Gdyby Turing nie dokonał swojego odkrycia, gdy to zrobił, rewolucja komputerowa mogłaby zostać opóźniona o dziesięciolecia.

DZIECI redaktor współpracujący Simson L. Garfinkel jest profesorem nadzwyczajnym informatyki w Naval Postgraduate School. Jego poglądy nie reprezentują oficjalnej polityki rządu Stanów Zjednoczonych ani Departamentu Obrony.

ukryć