Ekspresja po latach dwudziestych Kalkulator odnosi się do każdej maszyny, która wykonała pracę ludzki komputer, zwłaszcza tych, które zostały opracowane zgodnie z skuteczne metody Kościół - teza Turinga. Teza ta jest sformułowana w następujący sposób: „Każdy algorytm można określić w postaci odpowiedniej maszyny Turinga lub definicji częściowo rekurencyjnej, a klasa funkcji obliczalnych pokrywa się z klasą funkcji częściowo rekurencyjnych oraz z klasą funkcji obliczalnych na maszynach Turinga ”. Innymi słowy, teza Churcha-Turinga jest definiowana jako hipoteza o naturze mechanicznych urządzeń obliczeniowych, takich jak komputery elektroniczne. Wszelkie obliczenia, które są możliwe, można wykonać na komputerze, pod warunkiem, że jest wystarczająco dużo czasu i miejsca do przechowywania.

Mechanizmy działające na obliczeniach z nieskończonością stały się znane jako typ analogowy. Wartości w takich mechanizmach były reprezentowane przez ciągłe wartości liczbowe, na przykład kąt obrotu wału lub różnica potencjałów elektrycznych.

W przeciwieństwie do maszyn analogowych, maszyny cyfrowe miały możliwość reprezentowania stanu wartości liczbowej i przechowywania każdej cyfry osobno. Maszyny cyfrowe używały różnych procesorów lub przekaźników przed wynalezieniem urządzenia RAM.

Nazwa Kalkulator od lat 40. zaczął być wypierany przez koncepcję komputer... Te komputery były w stanie wykonać obliczenia, które zwykli robić urzędnicy. Ponieważ od tego momentu wartości nie były już zależne od cech fizycznych (jak w maszynach analogowych), komputer logiczny oparty na sprzęcie cyfrowym był w stanie zrobić wszystko, co można było opisać. system czysto mechaniczny .

Maszyny Turinga zaprojektowano, aby formalnie zdefiniować matematycznie, co można obliczyć przy ograniczeniach mocy obliczeniowej. Jeśli maszyna Turinga może wykonać zadanie, to zadanie jest uważane za obliczalne przez Turinga. Turing skupił się głównie na zaprojektowaniu maszyny, która mogłaby określić, co można obliczyć. Turing doszedł do wniosku, że dopóki istnieje maszyna Turinga, która może obliczyć przybliżenie liczby, wartość ta jest policzalna. Ponadto maszyna Turinga może interpretować operatory logiczne, takie jak AND, OR, XOR, NOT i If-Then-Else, aby określić, czy

Często rozwiązujemy problemy o różnym stopniu złożoności: codzienne, matematyczne itp. Niektóre są łatwe do rozwiązania, niektóre musimy dużo przemyśleć, dla niektórych nigdy nie znajdujemy rozwiązania.

W ogólnym przypadku sposób rozwiązania problemu (jeśli istnieje) można opisać za pomocą skończonej liczby czynności elementarnych.

Na przykład rozwiązywanie równania kwadratowego:

Doprowadź równanie do postaci kanonicznej \ (a x ^ 2 + b x + c = 0 \)
Jeśli \ (a = 0 \), to to równanie liniowe z rozwiązaniem \ (x = \ frac (-c) (b) \). Problem został rozwiązany. W przeciwnym razie przejdź do kroku 3.
Oblicz dyskryminator \ (D = b ^ 2-4 a c \)
Oblicz rozwiązania równania \ (x_ (1,2) = \ frac (-b \ pm \ sqrt (D)) (2 a) \)... Problem został rozwiązany.

Możesz wprowadzić następującą intuicyjną koncepcję algorytmu:

Algorytm to zbiór instrukcji opisujących kolejność działań wykonawcy w celu osiągnięcia wyniku rozwiązania problemu w skończonej liczbie działań, dla dowolnego zestawu danych początkowych.

Nie jest to oczywiście ścisła definicja, ale opisuje istotę pojęcia algorytmu.

Algorytmy są kompilowane na podstawie konkretnego wykonawca, a zatem powinny być sporządzone w języku zrozumiałym dla wykonawcy.

Wykonawcą algorytmu może być osoba, komputer lub inna maszyna, np. krosno.

Podkreślono następujące właściwości algorytmów:

Dyskretność algorytmu powinna być pewną sekwencją odrębnych, jasno określonych kroków (działań). Każda z tych czynności musi być skończona w czasie. Determinizm na każdym kroku algorytmu, kolejny krok jest jednoznacznie określony przez aktualny stan systemu. W konsekwencji, na tych samych danych początkowych, algorytm zwraca za każdym razem te same wyniki, niezależnie od tego, ile razy jest wykonywany. Zrozumiałość Algorytm powinien być sformułowany w języku zrozumiałym dla wykonawcy. Gdyby nadchodzi na komputerze algorytm musi używać tylko tych poleceń, które są znane komputerowi i których wynik jest ściśle określony. Skończoność algorytm musi wykonać w skończonej liczbie kroków. Masowość algorytmu powinna mieć zastosowanie do różnych zestawów danych wejściowych. Innymi słowy, algorytm musi być odpowiedni do rozwiązywania klasa zadania. Wracając do kwadratowego przykładu, algorytm nadaje się do rozwiązania ze wszystkich równania kwadratowe, a nie tylko jeden lub więcej. Skuteczność algorytmu musi kończyć się pewnym wynikiem. Powiedzmy, rozwiązując problem lub dowiadując się, że nie ma rozwiązań. Jeśli algorytm nie prowadzi do wyniku, nie jest jasne, dlaczego w ogóle jest potrzebny.

Nie każdy sposób rozwiązania problemu to algorytm. Powiedzmy, że algorytm nie daje wyboru. Na przykład większość przepisów nie jest algorytmami, ponieważ używa zwrotów takich jak „sól do smaku”. W konsekwencji naruszony zostaje wymóg determinizmu.

Nie dla każdego problemu, dla którego istnieje rozwiązanie, istnieje również algorytm rozwiązania. Na przykład problem rozpoznawania obrazu jest nadal w dużej mierze nierozwiązany, a już na pewno nie przy użyciu rygorystycznego algorytmu. Jednak zastosowanie sieci neuronowych daje całkiem dobre rezultaty.

Zwykle są zestawy dla algorytmu dopuszczalny dane wejściowe. Dziwnie byłoby próbować zastosować algorytm rozwiązywania równań do gotowania obiadu lub odwrotnie.

Ponadto zestaw możliwych działań wykonawcy jest również ograniczony, ponieważ gdyby jakiekolwiek działania były dozwolone, to wśród nich musiałoby być również „nie do zaakceptowania”.

Ścisła definicja algorytmu

Definicja powyższego algorytmu nie jest ścisła. Stwarza to pewne trudności. W szczególności przy takiej definicji nie da się rygorystycznie udowodnić, czy dana klasa problemów jest rozwiązywalna przez algorytm.

Okazuje się, że jest klasa algorytmicznie nierozwiązywalne problemy- problemy, dla których nie można skomponować algorytmu rozwiązania. Aby jednak rygorystycznie udowodnić nierozstrzygalność algorytmiczną, najpierw musisz mieć rygorystyczną definicję algorytmu.

W latach 20-30 XX wieku nad problemem ścisłej definicji algorytmu pracowali różni matematycy, w szczególności Alan Turing, Emil Leon Post, Andrei Andreevich Markov, Andrei Nikolaevich Kolmogorov, Alonzo Church i inni. Ich praca ostatecznie doprowadziła do powstania i rozwoju teorii algorytmów, teorii rachunku różniczkowego i różnych podejść do rachunku różniczkowego, a nawiasem mówiąc, programowania w ogóle. Jednym z rezultatów ich pracy było pojawienie się kilku ścisłych definicji algorytmu, wprowadzanych na różne sposoby, ale równoważnych sobie.

Zastanowimy się szczegółowo nad definicją Turinga i powierzchownie przeanalizujemy równoważne definicje Posta, Kościoła i Markowa.

Maszyna Turinga

Aby wprowadzić formalną definicję algorytmu, Turing wymyślił i opisał abstrakcyjną maszynę obliczeniową zwaną maszyną liczącą Turinga lub po prostu maszyną Turinga.

Alan Turing (1912-1954)

Angielski matematyk, logik, kryptograf, prawdopodobnie pierwszy na świecie „haker”, był na czele informatyki i teorii sztucznej inteligencji. Wniósł znaczący wkład w zwycięstwo sił alianckich w II wojnie światowej.

Dane wejściowe dla maszyny Turinga to słowa skompilowany przy pomocy pewnego alfabet czyli zestaw postacie.

Efektem pracy maszyny Turinga są także słowa.

Słowo, do którego stosuje się algorytm, nazywa się Wejście... Słowo, które pochodzi z pracy weekend.

Zbiór słów, do których stosuje się algorytm, nazywa się zakres algorytmu.

Ściśle mówiąc, nie da się udowodnić, że dowolny przedmiot można przedstawić w postaci słów ułożonych w jakimś alfabecie - do tego potrzebna byłaby ścisła definicja przedmiotu. Możesz jednak sprawdzić, czy dowolny algorytm losowy, który działa na obiektach, może zostać przekształcony tak, aby działał na słowach bez zmiany istoty algorytmu.

Opis maszyny Turinga

Maszyna Turinga zawiera taśmę, która jest nieograniczona w obu kierunkach, podzielona na komórki oraz urządzenie sterujące (zwane również głowica do odczytu i zapisu, lub po prostu maszyna), zdolny do przebywania w jednym z wielu stanów. Liczba możliwych stanów urządzenia sterującego jest skończona i precyzyjnie określona.

Urządzenie sterujące może poruszać się w lewo iw prawo wzdłuż taśmy, czytać i zapisywać znaki jakiegoś skończonego alfabetu do komórek. Przydzielony jest specjalny pusty znak, oznaczony \ (a_0 \) lub \ (\ Lambda \), który wypełnia wszystkie komórki taśmy, z wyjątkiem tych z nich (liczba skończona), na których zapisywane są dane wejściowe.

Sterownik działa zgodnie z regułami przejścia, które reprezentują algorytm realizowany przez daną maszynę Turinga. Każda reguła przejścia nakazuje maszynie, w zależności od bieżącego stanu i symbolu obserwowanego w bieżącej komórce, zapisanie nowego symbolu w tej komórce, przejście do nowego stanu i przesunięcie o jedną komórkę w lewo lub w prawo. Niektóre stany maszyny Turinga można oznaczyć jako terminalne, a przejście do dowolnego z nich oznacza koniec pracy, zatrzymanie algorytmu.

Chociaż maszyna Turinga jest pojęciem abstrakcyjnym, wystarczy sobie taką maszynę sobie po prostu wyobrazić (choć z skończoną taśmą), a są nawet takie maszyny demonstracyjne:

Wygodnie jest przedstawić algorytm dla maszyny Turinga w postaci tabeli: kolumny tabeli odpowiadają aktualnemu (obserwowanemu) symbolowi na taśmie, wiersze odpowiadają aktualnemu stanowi maszyny, a komórki zawierają polecenie, które ma wykonać maszyna.

Z kolei polecenie może mieć następującą strukturę:

\ [a_k \ left \ lbrace \ begin (macierz) L \\ N \\ R \ end (macierz) \ right \ rbrace q_m \]

Najpierw pojawia się symbol alfabetu, który należy wpisać w bieżącej komórce \ (a_k \), następnie ruch maszyny w lewo (L), w prawo (P) lub nigdzie (pozostań na miejscu, H) jest wskazany. Na koniec wskazany jest nowy stan, w który powinien wejść automat \ (q_m \).

Komórka tabeli jest wyraźnie określona przez bieżący symbol \ (a_i \) i bieżący stan maszyny \ (q_j \).

Umówmy się, że na początku pracy maszyna Turinga jest w stan początkowy, oznaczony przez \ (q_1 \), a po przejściu do stan zatrzymania\ (q_0 \) algorytm jest zakończony i maszyna zatrzymuje się.

Przykład

Skomponujmy algorytm dla maszyny Turinga, który dodaje 1 do słowa wejściowego, które jest liczbą dziesiętną.

Następnie opisowo algorytm można sformułować w następujący sposób:

Przesuwając się w prawo, znajdź początek słowa wejściowego
Przesuwając się w prawo, znajdź koniec słowa wejściowego
Dodaj jeden do bieżącego bitu słowa wejściowego. Jeśli jest liczba od 0 do 8, wyjdź. W przeciwnym razie wpisz 0, przesuń się w lewo i wróć do kroku 3.

Zapiszmy ten algorytm w formie tabeli. Alfabet składa się z cyfr od 0 do 9 oraz znaku pustego \ (\ Lambda \). Potrzebne są również 4 stany automatu liczące stan stopu, odpowiadające krokom w opisie algorytmu.

Zgódźmy się, że stan początkowy \ (1 \) to wyszukiwanie początku słowa wejściowego, \ (2 \) to wyszukiwanie końca słowa wejściowego, \ (3 \) to dodawanie 1.

\ (_ (q_j) \ ukośnik odwrotny ^ (a_i) \)	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛП1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	ΛЛ3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

Prześledźmy działanie tego algorytmu na przykładzie. Pierwsza linia odpowiada taśmie, druga wskazuje pozycję maszyny i jej aktualny stan.

	1	9	9
1

W stanie 1 automat znajduje się nad pustą komórką. Odpowiednie polecenie z tabeli „ΛП1”, czyli pozostaw komórkę pustą, przesuń się w prawo i pozostań w stanie 1:

	1	9	9
	1

Teraz automat monitoruje wartość „1”. Odpowiednia komenda „1H2”, czyli zostaw „1” w komórce, nie ruszaj się i przejdź do stanu „2”:

	1	9	9
	2

W stanie „2” maszyna obserwuje wartość „1”. Odpowiednie polecenie „1P2”, czyli pozostawić „1”, przesunąć się w prawo i pozostać w stanie „2”:

Sytuacja się powtarza:

Teraz w stanie 3 i przestrzegając symbolu „9”, maszyna wykonuje polecenie „0L3”:

	1	9	0
		3

Sytuacja się powtarza:

Stan „0” - stan zatrzymania. Algorytm został ukończony.

Opis formalny

Matematycznie maszynę Turinga można opisać w następujący sposób:

Maszyna Turinga (MT)

to jest system formy \ (\ (A, a_0, Q, q_1, q_0, T, \ tau \) \), gdzie

\ (A \) - skończony zbiór symboli alfabetu MT
\ (a_0 \ in A \) - pusty znak alfabetu
\ (Q \) jest skończonym zbiorem stanów MT
\ (q_1 \ in Q \) - stan początkowy MT
\ (q_0 \ in Q \) - stan końcowy MT (stan zatrzymania)
\ (T = \ (A, P, H \) \) to zbiór przesunięć MT
\ (\ tau \) - program MT, czyli funkcja określająca mapowanie \ (\ tau: A \ razy Q \ ukośnik odwrotny \ (q_0 \) \ strzałka w prawo A \ razy T \ razy Q \)

Kluczem w teorii algorytmów jest Teza Turinga.

Swobodnie sformułowana teza Turinga jest sformułowana w następujący sposób:

Teza Turinga dla każdego problemu, który można rozwiązać algorytmicznie, istnieje maszyna Turinga, która rozwiązuje ten problem. w przeciwnym razie dla dowolnego algorytmu istnieje równoważna maszyna Turinga.

Teza Turinga pozwala mówić o algorytmach za pomocą dość prostego aparatu matematycznego. Co więcej, sama maszyna Turinga jest uniwersalny siłownik, a sama możliwość stworzenia takiej wyimaginowanej maszyny stała się powodem do rozmowy o stworzeniu uniwersalnej technologii obliczeniowej.

Alternatywne definicje algorytmów

Oprócz maszyny Turinga istnieje kilka niezależnych definicji, które są równoważne definicji Turinga.

W szczególności definicja poprzez maszynę Post, poprzez kościelny rachunek lambda, normalny algorytm Markowa.

Rozważmy te metody.

Maszyna pocztowa

Rok po Turingu amerykański matematyk Emile Leon Post niezależnie zaproponował inną abstrakcyjną uniwersalną maszynę obliczeniową, która jest nieco uproszczona w porównaniu z maszyną Turinga.

Automat pocztowy działa z dwucyfrowym alfabetem, a stan wewnętrzny automatu jest zastępowany przez linia programu.

W przeciwnym razie maszyna Post jest podobna do maszyny Turinga: jest automat i jest niekończąca się taśma z komórkami.

Maszyna pocztowa może wykonywać następujące polecenia:

Napisz 1, przejdź do i-tej linii programu
Wpisz 0, przejdź do i-tego wiersza programu
Przesuń w lewo, przejdź do i-tej linii programu
Przesuń w prawo, przejdź do i-tej linii programu
Skok warunkowy: jeśli w obserwowanej komórce jest 0, przejdź do i-tej linii programu, w przeciwnym razie przejdź do j-tej linii programu.
Zatrzymać.

Maszyna pocztowa ma również kilka zabronionych poleceń:

Zapis do komórki 1, gdy jest już 1.
Zapis do komórki 0, gdy jest już 0.

Takie wydarzenia prowadzą do katastrofy.

Aby pisać programy dla maszyny pocztowej, możesz użyć następującej notacji:

∨ i - wpisz 1, przejdź do i-tego wiersza programu
× i - wpisz 0, przejdź do i-tego wiersza programu
← i - wykonaj przesunięcie w lewo, przejdź do i-tej linii programu
→ i - wykonaj przesunięcie w prawo, przejdź do i-tej linii programu
? i; j - skok warunkowy: jeśli w obserwowanej komórce jest 0, przejdź do i-tej linii programu, w przeciwnym razie przejdź do j-tej linii programu.
! - zatrzymać.

Przykładowy program:

1. → 2 2.? 1; 3 3. × 4 4. ← 5 5.!

Ten program usunie pierwszą etykietę (1) znajdującą się po prawej stronie pozycji początkowej maszyny i zatrzyma maszynę w komórce po lewej stronie.

Ogólnie rzecz biorąc, samochód Posta jest poprzednikiem tryb rozkazujący języki programowania, na przykład C, Fortran itp.

Maszyna Post jest odpowiednikiem maszyny Turinga. Innymi słowy, dla dowolnego programu dla maszyny Turinga można napisać równoważny program dla maszyny Post i na odwrót.

Jedną z ważnych konsekwencji tej równoważności jest to, że dowolny alfabet można zredukować do kodu binarnego.

Podobnie jak w przypadku tezy Turinga, istnieje również teza Posta.

Teza posta dowolny algorytm może być reprezentowany w postaci maszyny Post.

Normalny algorytm Markowa

Zwykłe algorytmy Markowa są przeznaczone do stosowania do słów w różnych alfabetach.

Definicja dowolnego normalnego algorytmu składa się z dwóch części:

Alfabet algorytm
Schematy algorytm

Sam algorytm jest stosowany do słowa czyli ciągi znaków alfabet.

Schemat normalnego algorytmu nazywamy skończonym uporządkowanym zbiorem tzw formuły podstawienia, z których każdy może być prosty lub finał... Wyrażenia postaci \ (L \ do D \) nazywane są prostymi formułami podstawienia, gdzie \ (L \) i \ (D \) to dwa dowolne słowa złożone z alfabetu algorytmu (nazywane odpowiednio lewym i prawym strony wzoru podstawienia). Podobnie końcowe formuły podstawienia są wyrażeniami postaci \ (L \ do \ cdot D \), gdzie \ (L \) i \ (D \) to dwa dowolne słowa złożone z alfabetu algorytmu.

Zakłada się, że znaki pomocnicze \ (\ do \) i \ (\ do \ cdot \) nie należą do alfabetu algorytmu.

Proces zastosowania normalnego algorytmu do dowolnego słowa \ (V \) to następująca sekwencja działań:

Niech \ (V "\) będzie słowem uzyskanym w poprzednim kroku algorytmu (lub oryginalnym słowem, jeśli bieżący krok jest pierwszym).
Jeśli nie ma podstawienia wśród formuł podstawień, których lewa strona byłaby zawarta w \ (V "\), wówczas praca algorytmu jest uważana za zakończoną, a wynikiem tej pracy jest słowo \ (V" \ ).
W przeciwnym razie wśród formuł podstawienia, których lewa strona jest zawarta w \ (V "\), wybierany jest pierwszy.
Ze wszystkich możliwych reprezentacji słowa \ (V "\) w postaci \ (RLS \) (gdzie \ (R \) jest prefiksem, a \ (L \) jest sufiksem), jedna jest wybrana tak, że \ ( R \) jest najkrótszym, po którym następuje podstawienie \ (V "= RDS \).
Jeśli formuła podstawienia była skończona, algorytm jest uzupełniany wynikiem \ (V "\). W przeciwnym razie przejdź do kroku 1 (następny krok).

Każdy normalny algorytm jest odpowiednikiem jakiejś maszyny Turinga i na odwrót - każda maszyna Turinga jest odpowiednikiem jakiegoś normalnego algorytmu.

Analogicznie do tezy Turinga o normalnych algorytmach nazywa się zwykle zasada normalizacji.

Przykład

Algorytm ten konwertuje liczby binarne na „jedynki” (w których zapis nieujemnej liczby całkowitej N jest ciągiem N drążków). Na przykład liczba binarna 101 jest konwertowana na 5 drążków: |||||.

Alfabet: (0, 1, |) Zasady:

1 → 0|
|0 → 0||
0 -> (pusty ciąg)

Oryginalna linia: 101 Wykonanie:

0|00|
00||0|
00|0|||
000|||||
00|||||
0|||||
|||||

Funkcje rekurencyjne

System równoważny maszynie Turinga można zbudować na podstawie funkcji matematycznych. W tym celu musimy wprowadzić następujące klasy funkcji:

prymitywne funkcje rekurencyjne
ogólne funkcje rekurencyjne
częściowo rekurencyjne funkcje

Ta ostatnia klasa będzie pokrywać się z klasą funkcji obliczanych przez Turinga (to znaczy funkcji, które można obliczyć, konstruując algorytm dla maszyny Turinga).

Definicja algorytmu poprzez funkcje rekurencyjne jest de facto istotą rachunku lambda i na jej podstawie budowane jest podejście programowanie funkcjonalne.

Prymitywne funkcje rekurencyjne

Klasa pierwotnych funkcji rekurencyjnych zawiera podstawowe funkcje oraz wszystkie funkcje wyprowadzone z funkcji bazowych za pomocą operatorów substytucje oraz prymitywna rekurencja.

Podstawowe funkcje obejmują:

Funkcja null \ (O () = 0 \) to funkcja bez argumentów, która zawsze zwraca \ (0 \).
Funkcja następstwa \ (S (x) = x + 1 \) jest funkcją, której dowolna Liczba naturalna\ (x \) odpowiada następującej liczbie \ (x + 1 \)
Funkcje \ (I_n ^ m (x_1, \ ldots, x_n) = x_m \), gdzie \ (0

Do skonstruowania pozostałych funkcji klasowych używa się operatorów:

Zastępstwa. Dla funkcji \ (f \) ze zmiennych \ (m \) i funkcji \ (m \) \ (g_1, \ ldots, g_m \) ze zmiennych \ (n \) każdy wynik podstawienia \ (g_k \) w \ ( f \) jest funkcją \ (h (x_1, \ ldots, x_n) = f (g_1 (x_1, \ ldots, x_n), \ ldots, g_m (x_1, \ ldots, x_n)) \) ze zmiennych \ (n \).
Rekurencja pierwotna. Niech \ (f (x_1, \ ldots, x_n) \) będzie funkcją \ (n \) zmiennych, a \ (g (x_1, \ ldots, x_ (n + 2)) \) funkcją \ (n + 2 \) zmienne. Wtedy wynikiem zastosowania pierwotnego operatora rekurencji do funkcji \ (f \) i \ (g \) jest funkcja \ (h \) zmiennej \ (n + 1 \) postaci: \ [h (x_1, \ ldots, x_n, 0) = f (x_1, \ ldots, x_n) \] \ [h (x_1, \ ldots, x_n, y + 1) = g (x_1, \ ldots, x_n, y, h (x_1, \ ldots, x_n, y)) \]

Funkcje częściowo rekurencyjne

Klasa częściowo rekurencyjnych funkcji obejmuje prymitywne funkcje rekurencyjne oraz dodatkowo wszystkie funkcje, które uzyskuje się z prymitywnych funkcji rekurencyjnych przy użyciu operatora minimalizacji argumentów:

Operator minimalizacji argumentów

Niech \ (f \) będzie funkcją \ (n \) zmiennych \ (x_i \ in \ mathbb (N) \). Następnie wynikiem zastosowania operatora minimalizacji argumentu do funkcji \ (f \) jest funkcja \ (h \) z argumentu \ (n-1 \), zdefiniowana jako:

\ [h (x_1, \ ldots, x_ (n-1)) = \ min y, \] gdzie \ Oznacza to, że \ (h \) zwraca minimalną wartość ostatniego argumentu funkcji \ (f \), przy której \ (f \) wynosi zero.

Chociaż funkcje pierwotne rekurencyjne są zawsze obliczalne, funkcje częściowo rekurencyjne mogą nie być zdefiniowane dla niektórych wartości argumentów.

Bardziej ściśle, częściowo rekurencyjne funkcje powinny być nazywane „częściowo zdefiniowanymi funkcjami rekurencyjnymi”, ponieważ są one zdefiniowane tylko na ułamku możliwych wartości argumentów.

Ogólne funkcje rekurencyjne

Ogólne funkcje rekurencyjne są podklasą wszystkich funkcji częściowo rekurencyjnych, które są zdefiniowane dla dowolnej wartości argumentu. Problem określenia, czy dana funkcja częściowo rekurencyjna jest ogólnie rekurencyjna, to algorytmicznie nierozwiązywalne... To prowadzi nas do tematu teorii obliczalności i problemu zatrzymania.

Teoria obliczalności i problem zatrzymania

Nasza wyobraźnia generalnie dopuszcza istnienie problemów nierozwiązywalnych, czyli takich, dla których nie da się ułożyć algorytmu.

Teoria obliczalności zajmuje się takimi problemami.

Przykładami algorytmicznie nierozwiązywalnych problemów są przestań problem oraz problem z rozpoznaniem lęgowości... Rozważmy je bardziej szczegółowo.

Zatrzymanie problemu Na podstawie opisu algorytmu A i danych wejściowych \ (x \) należy sprawdzić, czy algorytm \ (A \) zatrzymuje się na danych wejściowych \ (x \).

Problem zatrzymania jest algorytmicznie nierozwiązywalny. Udowodnijmy to.

\ (\ Delta \)

Niech będzie uniwersalny algorytm, który rozwiąże problem zatrzymania. Rozważmy zatem klasę algorytmów przetwarzających teksty opisujące algorytmy.

Ze względu na istnienie uniwersalnego algorytmu rozwiązywania problemu zatrzymania, istnieje algorytm, który określa, czy algorytm ze wspomnianej klasy zatrzyma się na własnym tekście, czy nie. Oznaczmy taki algorytm przez \ (B \).

Skonstruujmy algorytm \(C\), którego danymi wejściowymi jest tekst algorytmu \(A\), który przetwarza własny tekst:

Wykonaj algorytm \ (B \) nad \ (A \).
Jeśli algorytm \ (B \) ustali, że \ (A \) zatrzyma się na swoim tekście, przejdź do kroku 1. W przeciwnym razie przejdź do kroku 3.
Koniec algorytmu \ (C \).

Próbując zastosować algorytm \ (C \) do algorytmu \ (C \), dochodzimy do oczywistej sprzeczności: jeśli \ (C \) zatrzymuje się na swoim własnym tekście, to nie może się zatrzymać i odwrotnie. Dlatego nie ma algorytmu \ (B \). \ (\ nie \ Delta \)

Bardziej ogólnym sformułowaniem problemu zatrzymania jest problem zdefiniowania wykluwalności.

Problem z rozpoznaniem lęgowości

Niech zdefiniowany zostanie pewien alfabet, wyrazy (wzory) tego alfabetu i system formalnych przekształceń nad wyrazami tego alfabetu (tj. zbuduje się rachunek logiczny)

Czy dla dowolnych dwóch słów \ (R \) i \ (S \) istnieje łańcuch dedukcyjny prowadzący od \ (R \) do \ (S \) w ramach tego logicznego rachunku różniczkowego?

W 1936 r. Alonzo Church udowodnił twierdzenie Churcha.

Twierdzenie Church'a Problem rozpoznawania dedukowalności jest algorytmicznie nierozwiązywalny.

Church posłużył się formalizmem rachunku lambda, aby to udowodnić. W 1937, niezależnie od niego, Turing udowodnił to samo twierdzenie za pomocą formalizmu maszyny Turinga.

Ponieważ wszystkie definicje algorytmów są sobie równoważne, istnieje system pojęć, który nie jest powiązany z konkretną definicją algorytmu i operuje pojęciem funkcja obliczalna.

Funkcja obliczalna Funkcja, którą można obliczyć za pomocą algorytmu.

Istnieją problemy, w których relacji między danymi wejściowymi i wyjściowymi nie da się opisać za pomocą algorytmu. Takie funkcje są nieobliczalny.

Przykład funkcji nieobliczalnej

Weźmy funkcję \ (h (n) \) zdefiniowaną dla \ (\ forall n \ in \ mathbb (N) \) w następujący sposób:

\ [h (n) = \ begin (przypadki) 1, & \ text (jeśli w) \ pi \ text (jest ciąg dokładnie) n \ text (9-k) \\ 0, & \ text (w przeciwnym razie ) \ koniec (przypadki) \]

Możemy uzyskać wartość \ (1 \) dla tej funkcji, jednak aby uzyskać wartość \ (0 \), musimy sprawdzić nieskończone rozwinięcie dziesiętne liczby \ (\ pi \), co jest oczywiście niemożliwe w przypadku skończony czas. Ta funkcja jest zatem nieobliczalna.

Jednym z najważniejszych pytań współczesnej informatyki jest to, czy istnieje wykonawca formalny, za pomocą którego można naśladować każdego wykonawcę formalnego. odpowiedź na to pytanie uzyskali niemal jednocześnie dwaj wybitni naukowcy – A. Turing i E. Post. Zaproponowani przez nich wykonawcy różnili się od siebie, ale okazało się, że potrafili się naśladować, a co najważniejsze, naśladować pracę dowolnego formalnego wykonawcy.

Kim jest formalny wykonawca? Co to znaczy – jeden formalny wykonawca naśladuje pracę innego formalnego wykonawcy? Jeśli grałeś w gry komputerowe, obiekty na ekranie bez wątpienia słuchają poleceń gracza. Każdy obiekt ma zestaw prawidłowych poleceń. Jednocześnie sam komputer jest wykonawcą i nie wirtualnym, ale rzeczywistym. Okazuje się więc, że jeden formalny wykonawca naśladuje pracę innego formalnego wykonawcy.

Zastanów się, jak działa maszyna Turinga.

Maszyna Turinga to niekończąca się taśma podzielona na komórki oraz karetka (czytnik i drukarka), która porusza się wzdłuż taśmy.

Tak więc maszyna Turinga jest formalnie opisana za pomocą zestawu dwóch alfabetów:

A = (a1, a2, a3, ..., an) - alfabet zewnętrzny, używany do zapisu danych początkowych

Q = (q1, q2, q3,…, qm) - alfabet wewnętrzny, opisujący zbiór stanów czytnika i urządzenia drukującego.

Każda komórka taśmy może zawierać symbol z alfabetu zewnętrznego A = (a0, a1, ..., an) (w naszym przypadku A = (0, 1))

Prawidłowe działania maszyny Turinga są następujące:

1) wpisz dowolny znak alfabetu zewnętrznego do komórki taśmy (znak, który był tam wcześniej, zostanie nadpisany)

2) przejdź do sąsiedniej komórki

3) zmień stan na jeden ze wskazanych symbolem alfabetu wewnętrznego Q

Maszyna Turinga to maszyna napędzana stołem.

Wiersze w tabeli odpowiadają symbolom wybranego alfabetu A, a kolumny odpowiadają stanom automatu Q = (q0, q1,…, qm). Na początku działania maszyna Turinga znajduje się w stanie q1. Stan q0 jest stanem końcowym, gdy się do niego wejdzie, automat kończy swoją pracę.

Każda komórka tabeli odpowiadająca pewnemu symbolowi ai i pewnemu stanowi qj zawiera polecenie składające się z trzech części
Znak z alfabetu A
· Kierunek ruchu: ">" (w prawo), "<» (влево) или «.» (на месте)
Nowy stan maszyny

W powyższej tabeli alfabet A = (0, 1, _) (zawiera 3 znaki) oraz alfabet wewnętrzny Q = (q1, q2, q3, q4, q0), q0 to stan powodujący zatrzymanie karetki.

Rozważmy kilka zadań, rozwiązując. Maszynę Turinga można pobrać na stronie internetowej w dziale.

Zadanie 1. Niech A = (0, 1, _). Na taśmie komórki zawierają znaki z alfabetu w następującej kolejności 0011011. Karetka znajduje się nad pierwszym znakiem. Konieczne jest napisanie programu, który zastąpi 0 na 1, 1 na 0 i przywróci karetkę do pierwotnej pozycji.

Zdefiniujmy teraz stany wagonu. Nazywam je „powozem pragnienia czegoś zrobić”.

q1) Wagon musi jechać w prawo: jeśli widzi 0, zmienia je na 1 i pozostaje w stanie q1, jeśli widzi 1, zmienia je na 0 i pozostaje w stanie q1, jeśli widzi _, to odwraca 1 komórkę „chce czegoś innego”, czyli przechodzi do stanu q2. Zapiszmy nasze rozumowanie w tabeli wykonawcy. Zobacz pomoc programu dotyczącą składni)

q2) Teraz opisujemy „życzenie przewozu” q2. Musimy wrócić do naszej pierwotnej pozycji. Aby to zrobić: jeśli widzimy 1, zostaw je i pozostań w stanie q2 (z taką samą chęcią dotarcia do końca rzędu symboli); jeśli widzimy 0, opuszczamy je i kontynuujemy ruch w lewo w stanie q2; widzimy _ - jest przesunięty w prawo o 1 komórkę. Tutaj jesteś w miejscu, w którym jest to wymagane w opisie problemu. przechodzimy do stanu q0.

Możesz obejrzeć pracę programu na wideo:

Zadanie 2. Dane: końcowa sekwencja 0 i 1 (01101011101). Należy je wypisać po tej sekwencji przez pustą komórkę i w tej kolejności zastąpić je 0. Na przykład:

Od 001101011101 otrzymujemy 000000000000 1111111.

Jak widać, po tej sekwencji zapisuje się siedem jedynek, a na ich miejscach są zera.

Przejdźmy do rozumowania. Określ, jakie stany są potrzebne do przewozu i ile.

q1) piła 1 - ustaw ją na zero i przejdź do innego stanu q2 (wprowadzany jest nowy stan, aby wózek nie zamieniał wszystkich jedynek na zera w jednym przejeździe)

q2) nic nie zmieniaj, przejdź na koniec sekwencji

q3) gdy karetka widzi pustą komórkę, robi krok w prawo i rysuje jedną, jeśli ją widzi, a następnie przechodzi do podpisania znaku na końcu. Jak tylko narysujemy jednostkę, przechodzimy do stanu q4

q4) przechodzimy przez jednostki pisemne bez zmiany czegokolwiek. Jak tylko dojdziemy do pustej komórki oddzielającej ciąg od jedynek, przechodzimy z nowego stanu q5

q5) w tym stanie przechodzimy do początku ciągu bez zmiany czegokolwiek. Dochodzimy do pustej komórki, odwracamy się i przechodzimy do stanu q1

Karetka przyjmie stan q0, gdy przejdzie w stanie q1 do końca tej sekwencji i napotka pustą komórkę.

Otrzymujemy następujący program:

Możesz obejrzeć pracę maszyny Turinga na poniższym filmie.

Maszyna Turinga to zbiór następujących obiektów

1) alfabet zewnętrzny A = (a 0, a 1,…, a n);
2) alfabet wewnętrzny Q = (q 1, q 2,…, q m) jest zbiorem stanów;
3) zestaw znaków kontrolnych (P, L, S)
4) nieskończoną w obu kierunkach taśmę podzieloną na komórki, z których w każdej dyskretnej chwili można zapisać tylko jeden znak z alfabetu A;
5) urządzenie sterujące mogące znajdować się w jednym z wielu stanów;

Symbolem pustej komórki jest zewnętrzna litera alfabetu a 0.

Wśród stanów wyróżnia się stan początkowy q 1, w którym maszyna zaczyna pracować, oraz końcowy (lub stan zatrzymania) q 0, w którym maszyna się zatrzymuje.

Urządzenie sterujące może poruszać się w lewo i w prawo wzdłuż taśmy, odczytywać i zapisywać w komórkach taśmy litery alfabetu A. Urządzenie sterujące działa zgodnie z następującymi poleceniami

q i a j> a p X q k

Wpis oznacza: jeżeli urządzenie sterujące jest w stanie qi, aw obserwowanej komórce jest zapisana litera aj, to (1) zamiast aj w komórce jest zapisana ap, (2) maszyna przechodzi do przeglądania następna prawa komórka z tej, która została właśnie wyświetlona, jeśli X = P, lub aby wyświetlić następną lewą komórkę, jeśli X = L, lub kontynuuje badanie tej samej komórki na taśmie, jeśli X = C, (3) urządzenie sterujące przechodzi w stan qk.

Ponieważ praca maszyny według stanu jest całkowicie określona przez jej stan q, in ten moment a zawartość komórki oglądanej w tym momencie, to dla każdej możliwej konfiguracji q i a j istnieje dokładnie jedna reguła. Nie ma żadnych reguł tylko co do stanu końcowego, w którym samochód się zatrzymuje. Dlatego program maszyny Turinga z zewnętrznym alfabetem A = (a0, a1,…, an) i wewnętrznym Q = (q1, q2,…, qm) zawiera co najwyżej m (n + 1) instrukcji.

Słowo w alfabecie A lub w alfabecie Q lub w alfabecie A Q to dowolny ciąg liter odpowiedniego alfabetu. Przez k-tą konfigurację rozumiemy obraz taśmy maszyny z utworzoną na niej informacją na początku k-tego kroku (lub słowem w alfabecie A napisanym na taśmie na początku k-tego kroku). kroku), wskazującą, która komórka jest oglądana na tym etapie iw jakim stanie jest samochód. Tylko finalne konfiguracje mają sens, tj. te, w których wszystkie komórki taśmy, z możliwym wyjątkiem liczby skończonej, są puste. Konfiguracja jest nazywana ostateczną, jeśli stan, w którym znajduje się maszyna, jest ostateczny.

Jeżeli jako początkową wybierzemy dowolną nieostateczną konfigurację maszyny Turinga, to praca maszyny będzie polegała na sekwencyjnym (krok po kroku) przekształceniu konfiguracji początkowej zgodnie z programem maszyny aż do osiągnięcia konfiguracji końcowej . Następnie pracę maszyny Turinga uważa się za zakończoną, a wynikiem pracy jest osiągnięta ostateczna konfiguracja.

Powiemy, że niepuste słowo b w alfabecie A (a 0) = (a 1, ..., an) jest odbierane przez maszynę w pozycji standardowej, jeśli jest zapisane w kolejnych komórkach taśmy, wszystkie inne komórki są puste, a maszyna patrzy na skrajną lewą lub skrajną prawą komórkę spośród tych, w których jest napisane słowo b. Pozycja standardowa nazywana jest pozycją początkową (końcową), jeśli maszyna, która odbiera słowo w pozycji standardowej, znajduje się w stanie początkowym q 1 (odpowiednio w stanie zatrzymania q 0).

Jeśli przetwarzanie słowa b przenosi maszynę Turinga do stanu końcowego, mówi się, że ma ono zastosowanie do b, w przeciwnym razie nie ma zastosowania do b (maszyna działa w nieskończoność)

Rozważmy przykład:

Biorąc pod uwagę maszynę Turinga z alfabetem zewnętrznym A = (0, 1) (tutaj 0 jest symbolem pustej komórki), alfabetem stanów wewnętrznych Q = (q 0, q 1, q 2) oraz z następującym schematem funkcjonalnym (program):

q 1 0> 1 l q 2;

q 1 1 > 0°C q 2;

q 2 0> 0 P q 0;

q 2 1 > 1 C q 1;

Ten program można napisać za pomocą tabeli

W pierwszym kroku działa polecenie: q 1 0> 1 Л q 2 (urządzenie sterujące znajduje się w stanie q1, aw obserwowanej komórce jest zapisana litera 0, zamiast 0 w komórce jest zapisana 1, głowica jest przesunięta w lewo, urządzenie sterujące przechodzi w stan q2), w wyniku czego na maszynie tworzona jest następująca konfiguracja:

Ostatecznie po wykonaniu polecenia q 2 0> 0 P q 0 tworzona jest konfiguracja

Ta konfiguracja jest ostateczna, ponieważ maszyna była w stanie zatrzymania q 0.

W ten sposób oryginalne słowo 110 jest przetwarzane przez maszynę na słowo 101.

Otrzymaną sekwencję konfiguracji można zapisać w krótszy sposób (zawartość obserwowanej komórki jest zapisywana na prawo od stanu, w którym aktualnie znajduje się maszyna):

11q 1 0 => 1q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

Maszyna Turinga to nic innego jak reguła (algorytm) przekształcania słów alfabetu A Q, tj. konfiguracje. Tak więc, aby zdefiniować maszynę Turinga, należy określić jej alfabet zewnętrzny i wewnętrzny, program oraz wskazać, który z symboli oznacza pustą komórkę i stan końcowy.

Maszyna Turinga (MT)- abstrakcyjny executor (abstrakcyjna maszyna obliczeniowa). Został zaproponowany przez Alana Turinga w 1936 roku w celu sformalizowania koncepcji algorytmu.

Maszyna Turinga jest rozszerzeniem maszyny stanów skończonych i według tezy Churcha - Turinga: zdolny do naśladowania wszystkich wykonawców(ustalając reguły przejścia), które w jakiś sposób realizują proces obliczeń krok po kroku, w którym każdy krok obliczeń jest dość elementarny.

Oznacza to, że każdy intuicyjny algorytm można zaimplementować za pomocą jakiejś maszyny Turinga.

Kolegium YouTube

1 / 5

✪ 09 - Wprowadzenie do algorytmów. Maszyna Turinga

✪ Maszyna Turinga - Alexander Shen

✪ Wykład 20: Maszyna Turinga

✪ Maszyna Turinga. Przykład pracy

✪ 16 – Obliczalność. Maszyny Turinga. Motywacja i przykłady

Napisy na filmie obcojęzycznym

Struktura maszyny Turinga

Maszyna Turinga zawiera nieograniczoną liczbę w obu kierunkach wstążka(Możliwe są maszyny Turinga, które mają kilka nieskończonych wstęg), podzielone na komórki i urządzenie sterujące(nazywany również głowica do odczytu i zapisu (GZCH)), zdolny do bycia w jednym z zbiór stanów... Liczba możliwych stanów urządzenia sterującego jest skończona i precyzyjnie określona.

Urządzenie sterujące może poruszać się w lewo iw prawo wzdłuż taśmy, czytać i zapisywać znaki jakiegoś skończonego alfabetu do komórek. Wyróżnia się wyjątkowo pusty znak wypełniający wszystkie komórki taśmy, z wyjątkiem tych z nich (liczba skończona), na których zapisywane są dane wejściowe.

Urządzenie sterujące działa zgodnie z zasady przejścia które reprezentują algorytm, wykonalny ta maszyna Turinga. Każda reguła przejścia nakazuje maszynie, w zależności od bieżącego stanu i symbolu obserwowanego w bieżącej komórce, zapisanie nowego symbolu w tej komórce, przejście do nowego stanu i przesunięcie o jedną komórkę w lewo lub w prawo. Niektóre stany maszyny Turinga mogą być oznaczone jako terminal, a przejście do dowolnego z nich oznacza zakończenie pracy, zatrzymanie algorytmu.

Maszyna Turinga nazywa się deterministyczny jeśli co najwyżej jedna reguła pasuje do każdej kombinacji stanu i symbolu paska w tabeli. Jeśli istnieje para "symbol w paski - stan", dla której są 2 lub więcej instrukcji, nazywa się taką maszynę Turinga niedeterministyczny.

Opis maszyny Turinga

Konkretną maszynę Turinga określa się przez wyliczenie elementów zbioru liter alfabetu A, zbioru stanów Q oraz zbioru reguł, według których ta maszyna działa. Mają postać: qiaj → q i1 a j1 dk (jeśli głowa jest w stanie qi, a w obserwowanej komórce jest zapisana litera aj, to głowa przechodzi w stan q i1, w komórce jest zapisana j1 zamiast aj głowa wykonuje ruch dk, który ma trzy opcje: jedna komórka w lewo (L), jedna komórka w prawo (R), pozostań w miejscu (N)). Dla każdej możliwej konfiguracji istnieje dokładnie jedna zasada (dla niedeterministycznej maszyny Turinga może być: duża ilość zasady). Nie ma żadnych reguł tylko co do stanu końcowego, w którym samochód się zatrzymuje. Dodatkowo należy określić stan końcowy i początkowy, początkową konfigurację na taśmie oraz położenie głowicy maszyny.

Przykład maszyny Turinga

Podajmy przykład MT do mnożenia liczb w systemie liczb jednoargumentowych. Zapis reguły „qiaj → q i1 a j1 R / L / N” należy rozumieć następująco: qi to stan, w którym ta reguła jest wykonywana, aj to dane w komórce, w której znajduje się głowica, q i1 to stan, do którego należy przejść, a j1 - co należy wpisać do komórki, R / L / N - polecenie ruchu.

Maszyna działa zgodnie z następującym zbiorem zasad:

	q 0	q 1	q 2	q 3	q 4	q 5	q 6	q 7	q 8
1	q 0 1 → q 0 1R	q 1 1 → q 2 aR	q 2 1 → q 2 1L	q 3 1 → q 4 aR	q 4 1 → q 4 1R			q 7 1 → q 2 aR
×	q 0 × → q 1 × R		q 2 × → q 3 × L		q 4 × → q 4 × R		q 6 × → q 7 × R		q 8 × → q 9 × N
=			q 2 = → q 2 = L		q 4 = → q 4 = R			q 7 = → q 8 = L
a			q 2 a → q 2 aL	q 3 a → q 3 aL	q 4 a → q 4 aR		q 6 a → q 6 1R	q 7 a → q 7 aR	q 8 a → q 8 1L
*	q 0 * → q 0 * R			q 3 * → q 6 * R	q 4 * → q 5 1R
						q 5 → q 2 * L

Opis stanów:

Początek
q 0	stan początkowy. Szukamy "x" po prawej stronie. Po znalezieniu przechodzimy do stanu q1
q 1	zastępujemy „1” „a” i przechodzimy do stanu q2
Przenieś wszystkie „1” od pierwszej liczby do wyniku
q 2	szukam "x" po lewej stronie. Po znalezieniu przechodzimy do stanu q3
q 3	szukamy "1" po lewej stronie, zastępujemy "a" i przechodzimy do stanu q4. Jeśli „1” się skończyło, znajdujemy „*” i przechodzimy do stanu q6
q 4	idź do końca (szukając "" po prawej), zamień "" na "1" i przejdź do stanu q5
q 5	dodaj "*" na końcu i przejdź do stanu q2
Przetwarzamy każdą cyfrę drugiej liczby
q 6	poszukaj "x" po prawej i przejdź do stanu q7. Podczas wyszukiwania zastępujemy "a" "1"
q 7	szukam "1" lub "=" po prawej stronie po znalezieniu „1” zastępujemy go „a” i przechodzimy do stanu q2 po znalezieniu „=” przechodzimy do stanu q8
Kończyć się
q 8	szukam "x" po lewej stronie. Po znalezieniu przechodzimy do stanu q9. Podczas wyszukiwania zastępujemy "a" "1"
q 9	stan końcowy (algorytm stopu)

Pomnóż 3 przez 2 za pomocą MT w systemie jednostek. Protokół wskazuje stan początkowy i końcowy MT, początkową konfigurację na taśmie oraz lokalizację głowicy maszyny (symbol podkreślony).

Początek. Jesteśmy w stanie q 0, wprowadziliśmy dane do maszyny: * 111x11 = *, głowica maszyny znajduje się na pierwszym znaku *.

Pierwszy krok. Spójrzmy na tabelę reguł, co zrobi maszyna, gdy będzie w stanie q 0 i powyżej symbolu „*”. Jest to zasada z 1. kolumny 5. rzędu - q 0 * → q 0 * R. Oznacza to, że przechodzimy do stanu q 0 (czyli nie zmieniamy go), symbol staje się „*” (czyli nie zmienia się) i poruszamy się po wpisanym przez nas tekście „* 111x11 = *” w prawo o jedną pozycję (R), a następnie na 1. znaku 1. Z kolei stan q 0 1 (1. kolumna 1. wiersz) jest przetwarzany przez regułę q 0 1 → q 0 1R. Oznacza to, że znowu następuje po prostu przejście w prawo o 1 pozycję. Dzieje się tak, dopóki nie staniemy przy symbolu „x”. I tak dalej: bierzemy stan (indeks w q), bierzemy symbol, na którym stoimy (symbol podkreślony), łączymy je i obserwujemy przetwarzanie wynikowej kombinacji zgodnie z tabelą reguł.

W prostych słowach algorytm mnożenia wygląda następująco: zaznaczamy 1. jednostkę 2. czynnika, zastępując ją literą „a” i przenosimy cały 1. czynnik za znak równości. Przeniesienie odbywa się poprzez naprzemienne zastępowanie jednostek 1. czynnika przez „a” i dodawanie tej samej liczby jednostek na końcu wiersza (na lewo od prawego skrajnego „*”). Następnie zamieniamy wszystkie „a” na znak mnożenia „x” z powrotem na jedynki. I cykl się powtarza. W końcu A pomnożone przez B można przedstawić jako A + A + A B razy. Zaznaczamy teraz drugą jednostkę drugiego czynnika literą „a” i ponownie przenosimy jednostki. Jeśli nie ma jednostek przed znakiem „=”, mnożenie jest zakończone.

kompletność Turinga

Można powiedzieć, że maszyna Turinga to najprostsza maszyna obliczeniowa z pamięcią liniową, która zgodnie z formalnymi zasadami przetwarza dane wejściowe za pomocą sekwencji podstawowe czynności.

Elementarna natura akcji polega na tym, że akcja zmienia tylko niewielką część danych w pamięci (w przypadku maszyny Turinga tylko jedną komórkę), a liczba możliwych akcji jest skończona. Pomimo prostoty maszyny Turinga, można jej użyć do obliczenia wszystkiego, co można obliczyć na dowolnej innej maszynie, która wykonuje obliczenia za pomocą sekwencji podstawowych czynności. Ta właściwość nazywa się kompletność.

Jednym z naturalnych sposobów udowodnienia, że algorytmy obliczeniowe, które można zaimplementować na jednej maszynie, można zaimplementować na innej, jest naśladowanie pierwszej maszyny na drugiej.

Imitacja jest następująca. Opis programu (zasady działania) maszyny pierwszej podawany jest na wejście maszyny drugiej. D (\ styl wyświetlania D) i dane wejściowe X (\ styl wyświetlania X), które miały przybyć pod wejście do pierwszego samochodu. Konieczne jest opisanie takiego programu (zasad działania drugiej maszyny), aby w wyniku obliczeń wynik okazał się taki sam, jaki zwróciłaby pierwsza maszyna, gdyby otrzymała dane jako dane wejściowe X (\ styl wyświetlania X).

Jak zostało powiedziane, na maszynie Turinga można zasymulować (poprzez ustawienie reguł przejścia) wszystkie inne executory, które w jakiś sposób realizują proces obliczeń krok po kroku, w którym każdy krok obliczeń jest dość elementarny.

Na maszynie Turinga można naśladować maszynę Post, normalne algorytmy Markowa i dowolny program dla zwykłych komputerów, który konwertuje dane wejściowe na dane wyjściowe za pomocą jakiegoś algorytmu. Z kolei maszynę Turinga można naśladować na różnych abstrakcyjnych wykonawcach. Wykonawcy, dla których jest to możliwe, nazywają się Turing ukończony(Turing kompletny).

Istnieją programy na zwykłe komputery, które symulują działanie maszyny Turinga. Należy jednak zauważyć, że ta imitacja jest niekompletna, ponieważ w maszynie Turinga istnieje abstrakcyjna nieskończona taśma. Niekończąca się taśma z danymi nie może być w pełni zasymulowana na komputerze ze skończoną pamięcią (całkowita pamięć komputera wynosi Baran, dyski twarde, różne zewnętrzne nośniki pamięci, rejestry i pamięć podręczna procesora itp. - mogą być bardzo duże, ale jednak zawsze są skończone).

Warianty maszyny Turinga

Model maszyny Turinga jest rozszerzalny. Możemy rozważyć maszyny Turinga z dowolną liczbą taśm i taśmy wielowymiarowe z różnymi ograniczeniami. Jednak wszystkie te maszyny są kompletne pod względem Turinga i są modelowane przez konwencjonalną maszynę Turinga.

Maszyna Turinga działająca na półnieskończonym pasie

Jako przykład takiej redukcji rozważmy następujące twierdzenie: Dla każdej maszyny Turinga istnieje równoważna maszyna Turinga działająca na półnieskończonej taśmie (to znaczy na taśmie, która jest nieskończona w jednym kierunku).

Rozważmy dowód przedstawiony przez Yu G. Karpova w książce Theory of Automata. Dowód tego twierdzenia jest konstruktywny, to znaczy, podamy algorytm, za pomocą którego można zbudować równoważną maszynę Turinga o zadeklarowanej własności dla dowolnej maszyny Turinga. Najpierw arbitralnie numerujemy komórki taśmy roboczej MT, czyli definiujemy nową lokalizację informacji na taśmie:

Następnie przenumerujemy komórki i założymy, że symbolu „*” nie ma w słowniku MT:

Na koniec zmieniamy maszynę Turinga poprzez podwojenie liczby jej stanów oraz zmieniamy przesunięcie głowicy odczytująco-zapisującej tak, aby w jednej grupie stanów działanie maszyny było równoważne z jej działaniem w zacienionym obszarze, a w drugiej grupie stanów maszyna będzie działała tak jak oryginalna maszyna. w niezacienionym obszarze. Jeżeli podczas pracy MT napotkany zostanie symbol „*”, oznacza to, że głowica odczytująco-zapisująca osiągnęła granicę strefy:

Stan początkowy nowej maszyny Turinga jest ustawiany w jednej lub drugiej strefie, w zależności od tego, która część oryginalnej taśmy była głowicą odczytująco-zapisującą w oryginalnej konfiguracji. Oczywiście na lewo od znaczników ograniczających „*” taśma nie jest używana w równoważnej maszynie Turinga.

Dwuwymiarowe maszyny Turinga

mrówka Langtona

Zobacz też

Wieloplatformowy program JFLAP symulator automatów, maszyny Turinga, gramatyki, rysuje graf automatu