Wkład Alana Turinga w informatykę

Alan Turing , jeden z pionierów (teoretycznej) informatyki, wniósł znaczący wkład naukowy w naszą dziedzinę, w tym definiując maszyny Turinga, tezę Kościoła-Turinga, nierozstrzygalność i test Turinga. Jednak jego ważne odkrycia nie ograniczają się do tych, które wymieniłem.

Na cześć jego 100. urodzin pomyślałem, że byłoby miło poprosić o bardziej kompletną listę jego ważnych wkładów w informatykę, aby lepiej docenić jego pracę.

Jaki jest zatem ważny / wpływowy wkład Alana Turinga w informatykę?

To pytanie jest podobne do pytania o wkład Newtona w fizykę lub Darwina w biologię! Jest jednak interesujący aspekt pytania, na które wielu komentatorów już się zdecydowało: mianowicie, że oprócz ogromnego wkładu, o którym wszyscy wiedzą, istnieje wiele mniejszych wkładów, o których większość ludzi nie wie --- oraz wiele spostrzeżeń które uważamy za bardziej „nowoczesne”, ale Turing wykazał w różnych uwagach, że doskonale rozumie. (Nawiasem mówiąc, to samo dotyczy Newtona i Darwina).

Kilka przykładów, które lubię (oprócz tych wymienionych wcześniej):

W „Computing Machinery and Intelligence” Turing zawiera dość nowoczesną dyskusję na temat zalet losowych algorytmów:

Prawdopodobnie rozsądnie jest dołączyć losowy element do maszyny uczącej się. Element losowy jest raczej przydatny, gdy szukamy rozwiązania jakiegoś problemu. Załóżmy na przykład, że chcemy znaleźć liczbę między 50 a 200, która jest równa kwadratowi sumy jej cyfr, możemy zacząć od 51, a następnie spróbować 52 i kontynuować, aż otrzymamy liczbę, która zadziała. Alternatywnie możemy wybrać liczby losowe, dopóki nie otrzymamy dobrej. Zaletą tej metody jest to, że nie jest konieczne śledzenie wypróbowanych wartości, ale wadą jest to, że można wypróbować tę samą dwukrotnie, ale nie jest to bardzo ważne, jeśli istnieje kilka rozwiązań. Wadą metody systematycznej jest to, że może istnieć ogromny blok bez żadnych rozwiązań w regionie, które należy zbadać najpierw, Teraz proces uczenia się może być uważany za poszukiwanie formy zachowania, która spełni wymagania nauczyciela (lub innego kryterium). Ponieważ prawdopodobnie istnieje bardzo duża liczba zadowalających rozwiązań, metoda losowa wydaje się lepsza niż systematyczna. Należy zauważyć, że jest on wykorzystywany w analogicznym procesie ewolucji.

Najwyraźniej Turing był także pierwszą osobą, która za pomocą komputera cyfrowego szukała kontrprzykładów hipotezy Riemanna - patrz tutaj .

Oprócz wyników technicznych z rozprawy doktorskiej Turinga z 1939 r. (Wspomnianej przez Lwa Reyzina), ta rozprawa jest niezwykle godna uwagi przy wprowadzaniu pojęć wyroczni i relatywizacji do teorii obliczalności. (Niektórzy ludzie mogą żałować, że Turing nigdy tego nie zrobił, ale ja nie jestem jednym z nich :-D)

Wreszcie, chociaż jest to podstawowe, wydaje się, że nikt jeszcze nie wspomniał o istnieniu uniwersalnych maszyn Turinga - to wyraźny wkład w zdefiniowanie modelu maszyny Turinga, sformułowanie tezy Kościoła-Turinga lub udowodnienie nierozwiązywalności Entscheidungsproblem, ale prawdopodobnie najbardziej „bezpośrednio” związany z którymkolwiek z nich w toku rewolucji komputerowej.

Do niedawna o nich nie wiedziałem.

1) Rozkład macierzy LU wynika z Turinga! Biorąc pod uwagę, jak fundamentalny jest rozkład LU, jest to jeden wkład, który zasługuje na podkreślenie i szerzej znany (1948).

2) Turing jako pierwszy wymyślił „papierowy algorytm” szachowy. W tym momencie budowano pierwsze komputery cyfrowe (1952).

Programowanie szachowe ma znakomity zestaw ludzi związanych z nim, takich jak Shannon, Turing, Herb Simon, Ken Thompson itp. Dwa ostatnie zdobyły Nagrodę Turinga. I oczywiście Simom również zdobył Nobla. (Shannon wymyślił sposób oceny pozycji szachowej w 1948 r.)

Jak wspomniano w pytaniu, Turing był kluczowy w definiowaniu algorytmów i obliczalności, dlatego był jedną z osób, które pomogły zmontować soczewkę algorytmiczną. Myślę jednak, że jego największy wkład polegał na oglądaniu nauki przez soczewkę algorytmiczną, a nie tylko na obliczeniach.

Podczas II wojny światowej Turing wykorzystał ideę obliczeń i komputerów elektromechanicznych (w przeciwieństwie do ludzkich), aby pomóc w stworzeniu bomby Turinga-Welchmana oraz innych narzędzi i formalnych technik wykonywania kryptoanalizy. Rozpoczął transformację kryptologii, formy sztuki, w kryptografię, naukę, którą ukończył Claude Shannon. Alan Turing przeglądał kryptologię za pomocą soczewek algorytmicznych.

W 1948 r. Turing podążył za zainteresowaniem mózgiem, aby stworzyć pierwszą uczącą się sztuczną sieć neuronową . Niestety jego rękopis został odrzucony przez dyrektora NPL i nie został opublikowany (do 1967 r.). Jednak wyprzedził on zarówno naukę hebrajską (1949), jak i perceptrony Rosenblatta (1957), które zwykle kojarzyliśmy z byciem pierwszą siecią neuronową. Turing przewidział podstawy łączności (wciąż ogromny paradygmat w kognitywistyce) i neuronauki obliczeniowej. Alan Turing oglądał mózg przez soczewki algorytmiczne.

W 1950 r. Turing opublikował swoją słynną maszynę obliczeniową i inteligencję i uruchomił sztuczną inteligencję. Miało to transformujący wpływ na psychologię i kognitywistykę, które nadal postrzegają poznanie jako obliczenie reprezentacji wewnętrznych. Alan Turing patrzył na umysł przez soczewki algorytmiczne.

W końcu w 1952 roku (jak wspomniano @vzn) Turing opublikował The Chemical Basis of Morphogenesis. To stało się jego najczęściej cytowanym dziełem. W nim zadał (i zaczął odpowiadać) pytanie: w jaki sposób sferycznie symetryczny zarodek przekształca się w niesferycznie symetryczny organizm pod działaniem zachowującej symetrię chemicznej dyfuzji morfogenów? Jego podejście w tym artykule było bardzo fizykalne, ale niektóre z nich miały charakter TCS; Jego praca zawierała rygorystyczne stwierdzenia jakościowe (ważne dla różnych stałych i parametrów) zamiast stwierdzeń ilościowych opartych na określonych (w niektórych dziedzinach: potencjalnie niemożliwych do zmierzenia) stałych i parametrów. Krótko przed śmiercią kontynuował badania, pracując nad podstawowymi pomysłami na symulacje sztucznego życia, a także bardziej dyskretne i niejednoznaczne traktowanie biologii. W poście na bloguSpekuluję, jak rozwinąłby biologię, gdyby miał więcej czasu. Alan Turing zaczął patrzeć na biologię za pomocą soczewek algorytmicznych.

Myślę, że największym (i często ignorowanym) wkładem Turinga w informatykę było pokazanie, że możemy uzyskać wspaniały wgląd, patrząc na naukę przez soczewkę algorytmiczną. Mogę tylko mieć nadzieję, że uszanujemy jego genialność, kontynuując jego pracę.

Powiązane pytania

• Soczewka algorytmiczna w naukach społecznych

• Nowoczesne metody leczenia sieci neuronowych typu B Alana Turinga

• Wpływ podejścia Alana Turinga do morfogenezy

Mniej znany wkład to estymator Good-Turinga służący do oszacowania części populacji, której „jeszcze nie widać” podczas pobierania próbek. Jest to wykorzystywane w różnorodności biologicznej.

Artykuł Turinga na temat sprawdzania dużej rutyny, który został zaprezentowany na konferencji w Cambridge w 1949 r., Uzasadnia formalne rozumowanie programów opracowanych przez Floyda i Hoare'a przez prawie dwie dekady. Artykuł ma tylko trzy strony i zawiera pomysł użycia niezmienników do udowodnienia właściwości programów oraz zasadności udowodnienia zakończenia.

Jak można sprawdzić procedurę, upewniając się, że jest odpowiednia?

Aby człowiek sprawdzający nie miał zbyt trudnego zadania, programista powinien poczynić szereg określonych stwierdzeń, które można sprawdzić indywidualnie i na podstawie których łatwo można sprawdzić poprawność całego programu.

Turing był zainteresowany i wykonał kilka znaczących prac nad wzorcami reakcji chemicznej-dyfuzji. ten obszar badań znacznie się poszerzył, odkąd zaczął go badać. wykazano, że ma powiązania z obliczalnościami, np. jest w pewnym sensie „zakończony Turing” [1]. reakcje chemiczne można modelować za pomocą złożonych nieliniowych równań różniczkowych, więc w pewnym sensie wykazano, że nieliniowe równania różniczkowe o wystarczającej złożoności mogą symulować maszyny Turinga. wynikające z jego artykułu z 1951 r. „chemiczne podstawy morfogenezy” [4]

[1] kinetyka chemiczna jest uniwersalna według Turinga przez Magnasco w PRL 97

[2] Struktury Turinga w prostych reakcjach chemicznych

[3] Wzorce Turinga w liniowych układach reakcji chemicznych z nieliniową dyfuzją krzyżową według Franza

[4] chemiczne podstawy morfogenezy, wikipedia

Oto kolejny, który znalazłem na blogu Scotta Aaronsona (i stamtąd pochodzi Q + A):

W swoim doktoracie praca, Turing studiował pytanie ( jest teorią):$F_α$

Biorąc pod uwagę maszynę Turinga która działa wiecznie, czy zawsze istnieje porządek α taki, że dowodzi, że działa wiecznie?$M$$F_α$$M$

Turing udowodnił:

Biorąc pod uwagę każdą maszynę Turinga która działa wiecznie, istnieje kodowanie jej aksjomatów ( ), które dowodzą, że działa wiecznie.$M$$F_{\omega+1}$$M$

Niestety definicje i szczegóły techniczne są trudniejsze do podsumowania, ale link do postu na blogu dobrze je wyjaśnia.

tutaj jest szeroka, wysoce zbadana / szczegółowa ankieta online 9p / retrospektywa specyficznego i bardziej ogólnego / długofalowego wkładu Turinga w Notices of the American Mathematical Society autorstwa SB Coopera z okazji 100. rocznicy, Niezliczalność po Alanie Turingu . niektóre inne wypowiedzi wymienione w tym badaniu:

• Błędy zaokrąglania w papierze z procesami macierzowymi , 1948. wpływające na analizę numeryczną i obliczenia naukowe w teorii obliczeń

• niepublikowany raport National Physical Laboratory z 1948 r. Intelligent Machinery opisuje wczesny model połączenia , podobny i współczesny ze słynnymi sieciami neuronowymi McCulloch i Pitts .

• Wskazuje, że analizę Turinga i teorię morfogenezy można uznać za wczesną intelektualną podstawę masywnej (i wciąż trwającej / aktywnej) późniejszej teorii w samoorganizacji i powstających zjawiskach .

(itp)