Uniwersalna maszyna Turinga

W informatyce , a dokładniej w informatyce teoretycznej , uniwersalna maszyna Turinga to maszyna Turinga, która może symulować dowolną maszynę Turinga na dowolnym wejściu. Maszyna uniwersalna przyjmuje jako dane wejściowe opis symulowanej maszyny i dane wejściowe tej ostatniej.

Alan Turing wynalazł taką maszynę w 1936 roku. Ta maszyna jest uważana przez niektórych (na przykład Martina Davisa ) za początek nagranego programu komputerowego zaprojektowanego przez Johna von Neumanna (1946), który teraz nosi jego imię: architektura von Neumanna .

Zasada uniwersalnej maszyny Turinga

Maszyna Turinga

Maszyna Turinga to model obliczeniowy składający się z systemu przejść, wstążki i głowicy odczytująco-zapisującej. Po podaniu słowa wejściowego m maszyna wykonuje elementarne operacje obliczeniowe: odczytuje znak, zapisuje znak, przesuwa głowicę odczytu/zapisu w lewo lub w prawo od komórki. Jeśli maszyna się zatrzyma, nazywamy f (m) zawartością wstążki. W przeciwnym razie, jeśli maszyna zapętla się, f (m) nie jest zdefiniowane. W ten sposób maszyna oblicza wynik funkcji cząstkowej f . W tym sensie maszyna Turinga zachowuje się jak komputer z określonym programem.

Pochodzenie uniwersalnej maszyny Turinga

Turing zaprojektował swoją uniwersalną maszynę do badania problemu postawionego przez Davida Hilberta w 1928 roku: Entscheidungsproblem , problem decyzyjny . Problem ten został sformułowany w ramach programu Hilberta, którego celem było zabezpieczenie podstaw matematyki, poprzez rygorystyczną aksjomatyzację różnych gałęzi tej dziedziny. Ten program określa trzy najważniejsze osie, które mają udowodnić fundament solidnego systemu matematycznego, a mianowicie:

Entscheidungsproblem jest właśnie próbą sformalizowania problemu rozstrzygalności za pomocą formalizmu opracowanego przez Gottloba Fregego , rachunku predykatów . Jednym z możliwych stwierdzeń tego problemu jest:

Znajdź algorytm, który określa, czy zdanie podane w formalizmie rachunku predykatów jest poprawne , tj. prawdziwe, niezależnie od semantyki obiektów i relacji, które realizuje.

Teraz na scenę wkraczają logicy Alonzo Church i Alan Turing .

Chcąc odpowiedzieć negatywnie na problem decyzyjny postawiony przez Hilberta, Church definiuje rachunek lambda , pierwszą teorię rygorystycznie określającą, co jest skuteczną „metodą” lub „procedurą” rozwiązywania problemu i wykorzystującą pojęcia funkcji rekurencyjnych wprowadzone przez Jacquesa Herbranda i Kurta Gödla . Rzeczywiście udowodnił absurdem, że ogólna metoda rozstrzygania, czy orzeczenie jest poprawne, czy nie, nie może istnieć.

Tymczasem Alan Turing stworzył koncepcję maszyn Turinga w tym samym celu, niezależnie od Kościoła, w tym samym roku. Udaje mu się również wykazać, że istnieją zdania, których ważności nie można określić algorytmem, podkreślając problem zatrzymania .

Kodowanie maszyny Turinga

Ale, jak opisał to Alan Turing , możemy zakodować tablicę akcji maszyny Turinga w postaci ciągu znaków. Możemy zatem pokusić się o zbudowanie maszyny Turinga, która zakłada istnienie na swojej wstążce ciągu znaków kodujących tablicę akcji, po której następuje ciąg znaków stanowiących dane efektywne wstążki i oblicza zawartość taśmy, którą zakodowała. Maszyna Turinga by obliczyła.

Jak wykazał Alan Turing w swoim przełomowym artykule, możliwe jest stworzenie takiej maszyny Turinga, a ponieważ może ona symulować zachowanie każdej innej maszyny Turinga, nazywa się ją „uniwersalną maszyną Turinga”.

Dzięki temu kodowaniu tablic akcji w postaci ciągów znaków, maszyny Turinga mogą w zasadzie odpowiadać na pytania dotyczące zachowania innych maszyn Turinga. Jednak większość z tych pytań jest nierozstrzygalna, tzn. funkcja, o której mowa, nie może zostać obliczona przez maszynę Turinga. Na przykład pytanie, czy maszyna Turinga w pewnym momencie osiąga stan wyłączenia, czy też nigdy nie robi tego dla określonego wejścia lub dla wszystkich możliwych danych wejściowych, znane jako problem z zamknięciem , okazało się nierozstrzygalne przez Turinga. Na Twierdzenie Rice'a pokazuje, że każda nieruchomość nietrywialna w języku zaakceptowanym przez maszynę Turinga jest nierozstrzygalny.

Uniwersalna maszyna Turinga to Turing-kompletna . Potrafi obliczyć dowolną funkcję rekurencyjną , przeanalizować dowolny język rekurencyjny i zaakceptować dowolny język częściowo rozstrzygający . Zgodnie z tezą Churcha-Turinga , problemy, które może rozwiązać uniwersalna maszyna Turinga, to dokładnie te problemy, które można rozwiązać algorytmem lub konkretną metodą obliczeń , przy założeniu rozsądnej definicji tych terminów.

Zarejestrowany komputer programu

Ten artykuł może zawierać nieopublikowane prace lub niezweryfikowane oświadczenia (Kwiecień 2021).

Możesz pomóc, dodając odniesienia lub usuwając nieopublikowane treści. Zobacz stronę dyskusji po więcej szczegółów.

Jeśli pojęcie zdolności do symulowania dowolnej innej maszyny tej samej klasy (np. maszyny Turinga w naszym przypadku) zostało wprowadzone na długo wcześniej, przez Charlesa Babbage i jego maszynę analityczną (która może symulować dowolną inną maszynę liczącą po zaprogramowaniu poprzez karty krosna żakardowego , stając się tym samym pierwszą koncepcją przypominającą komputer ogólnego przeznaczenia), uniwersalna maszyna Turinga wyznaczyła pionierskim producentom komputerów kolejny rewolucyjny pomysł, a mianowicie przechowywanie programów w pamięci, a nie na kartach, a więc możliwość ich modyfikacji.

Dzięki takiej architekturze maszyna może teraz zmieniać swoją tabelę akcji podczas akcji (ponieważ głowica może zarówno czytać, jak i pisać), a tym samym przeprogramować się.

Alan Turing mówi na ten temat:

„Chcemy maszyny, która uczy się na swoich doświadczeniach […], a możliwość pozwolenia maszynie na manipulowanie jej instrukcjami to dobry mechanizm. "

To było w 1945 roku, kiedy dołączył do National Physics Laboratory w Londynie pod kierownictwem Johna Womersleya , publikując pierwszy dokument wyszczególniający specyfikacje dla budowy uniwersalnego i zarejestrowanego komputera programowego, Automatic Computing Engine (ACE), prototypu z których po raz pierwszy został zbudowany w 1950 roku przez Edwarda Newmana , Jima Wilkinsona , Michaela Woodgera i innych ...

Von Neumann, który dopiero w 1944 roku dołączył do grupy konstrukcyjnej ENIAC kierowanej przez J. Prespera Eckerta i Johna Mauchly'ego , zaczął być coraz bardziej zaintrygowany uniwersalnymi maszynami Turinga.

W 1945 opublikował pierwszy projekt raportu EDVAC , który stał się pierwszym opublikowanym artykułem opisującym projekt komputera do architektury, którą znamy dzisiaj pod nazwą architektoniczną von Neumann. Niestety, EDVAC nie będzie w pełni operacyjny do 1951 roku.

Dopiero w 1948 roku Mała Eksperymentalna Maszyna Uniwersytetu w Manchesterze (SSEM), zbudowana przez FC Williamsa i Toma Kilburna, stała się pierwszym elektronicznym „komputerem”, który uruchamiał program przechowywany w pamięci.

Ale SSEM nie jest uważany za ukończony komputer, ale raczej za dowód koncepcji koncepcji, to EDSAC z Cambridge otrzymuje tytuł „pierwszego cyfrowego komputera elektronicznego z kompletnym zarejestrowanym programem i działającym”. 6 maja 1949.

Symulacja maszyny Turinga

Ogólne pomysły

Ponieważ liczba stanów maszyny jest a priori skończona, Papadimitriou sugeruje reprezentowanie stanu przez liczbę całkowitą, a zatem reprezentowanie stanu przez binarną reprezentację tej liczby całkowitej .

Minimalizacja

Jeśli rozszerzymy definicję o maszyny Turinga, które symulują kompletne modele obliczeniowe Turinga , a nie tylko maszyny Turinga, które bezpośrednio symulują inne maszyny Turinga, uniwersalna maszyna Turinga może być stosunkowo prosta i używać tylko kilku stanów i symboli. Na przykład istnieje uniwersalna maszyna Turinga o rozmiarze 2 × 18 (tj. 2 stany i 18 symboli). Najmniejsze znane uniwersalne maszyny Turinga mają następujące rozmiary: 2×18, 3×10, 4×6,5×5, 7×4, 10×3, 22×2. Symulują one model zwany systemami znaczników .

Maszyna Turinga w rozmiarze 2×3, zaproponowana przez Stephena Wolframa , została ogłoszona najmniejszą uniwersalną maszyną Turinga. Dowód należy do Alexa Smitha. Jednak pojęcie uniwersalności użyte w tym dowodzie nie jest takie samo, jak opisane nieformalnie powyżej. W szczególności wymaga to napisania na wstążce nieskończonej liczby symboli, aby przygotować się do obliczeń.

Maszyna Turinga nie jest najlepszym sposobem na kompaktowe zakodowanie uniwersalnego komputera. Binarny lambda-rachunek  (en) jest narzędziem, które optymalizuje jego gęstość znacznie więcej. John Tromp, który jest jego źródłem, proponuje termin tego obliczenia, który koduje uniwersalny interpreter w 657 bitach informacji.

Bibliografia

  1. (i) AM Turinga , „  W obliczalną numerów, w aplikację do Entscheidungsproblem  ” , Proceedings of London PTM , obj.  s2-42, N O  1,1937, s.  230-265 ( ISSN  0024-6115 , DOI  10.1112 / plms / s2-42.1.230 , czytanie online , dostęp 11 maja 2018 )
  2. Harry R. Lewis i Christos Papadimitriou , Elementy teorii obliczeń , Prentice Hall Inc.,1998
  3. Martin Davis, Komputer uniwersalny: droga z Leibniza do Turinga , WW Norton,2000wydana w twardej oprawie w 2021 roku pod tytułem Engines of Logic .
  4. Martin Davis, „  Logika matematyczna i pochodzenie komputera  ”, Studia z historii matematyki ,1987, s.  135-165.
  5. Brian E. Blank, „  Review of` The Universal Computer: The Road from Leibniz to Turing`  ”, Notices of the AMS ,maj 2001, s.  498 ( czytaj online ).
  6. B. Jack Copeland , The Stanford Encyclopedia of Philosophy , Metaphysics Research Lab, Stanford University,2017( przeczytaj online )
  7. (w) Alonzo Church , „  Notatka o problemie decyzyjnym  ” , The Journal of Symbolic Logic , tom.  1, N O  1,Marzec 1936, s.  40-41 ( ISSN  0022-4812 i 1943-5886 , DOI  10.2307 / 2269326 , czytanie online , dostęp 11 maja 2018 )
  8. „  AlanTuring.net A Brief History of Computing  ” , na www.alanturing.net (dostęp 11 maja 2018 r. )
  9. John von Neumann , „  Pierwszy szkic raportu na temat EDVAC  ”, Roczniki IEEE Historii Informatyki , tom.  15 N O  4,1 st październik 1993, s.  27-75 ( ISSN  1058-6180 , DOI  10.1109 / 85.238389 , czytaj online , dostęp 11 maja 2018 )
  10. Reklama na stronie Wolfram 2,3 Turing Machine Research Prize .
  11. John Tromp, „  Binary Lambda Calculus and Combinatory Logic  ”, Kolmogorov Complexity and Applications 2006 ,2006( przeczytaj online ).

Załączniki

Powiązane artykuły

Bibliografia