Skład przykładów maszyn Turinga. Właściwa obliczalność funkcji na maszynie Turinga

Maszyna Turinga (MT) jest abstrakcyjnym wykonawcą (abstrakcyjną maszyną liczącą).

Kombinacje algorytmów to nazwa, która została ustalona dla szeregu konkretnych metod konstruowania nowych algorytmów z kilku podanych.

Twierdzenia o kombinacjach algorytmów stanowią ważny dział ogólnej teorii algorytmów. Po sprawdzeniu umożliwiają późniejszą weryfikację wykonalności złożonych i uciążliwych algorytmów bez konieczności pisania obwodów je definiujących.

Kombinacje algorytmów dla maszyny Turinga opisano operacjami na maszynach Turinga.

1. Operacja kompozycji.

Niech M 1 i M 2 będą maszynami Turinga posiadającymi ten sam zewnętrzny alfabet A« (a 0 , a 1 ,..., a p ). Oznaczmy zbiory ich stanów odpowiednio jako Q1 "(q 0,q 1,...,q n) i Q2 "(q 0",q 1",...,q m").

Definicja.

Układ maszyn M 1 i M 2 to maszyna oznaczona M=M 1 × M 2, której program ma alfabet A, zbiór stanów Q« (q 0,q 1,...,q n,q n+1,... ,q n+m) i otrzymuje się z programów maszyn M 1 i M 2 następująco: wszędzie w programie maszyny M 1, gdzie znajdują się „trójki” o symbolu q 1 ( stan końcowy maszyny M 1), zastępuje się go symbolem q 0" (stan początkowy maszyny M 2); wszystkie pozostałe symbole w programach maszyn M 1 i M 2 pozostają niezmienione (ostatecznie wszystko to pozostaje przenumerować wszystkie stany maszyny M: (q 0 ,q 1" ,q 2 ,...,q n ,q 0 " ,q 2" ,...,q m")).

Kompozycja zaczyna „pracować” jak maszyna M 1, lecz w przypadkach, gdy maszyna M 1 musi się zatrzymać, przełącza się na program maszyny M 2, w związku z zastąpieniem q 1 przez q 0”. Oczywiście, operacja składania jest asocjacyjna, ale nie przemienna.

Jego działanie jest równoznaczne z sekwencyjną pracą maszyn T1 i T2.

Rysunek przedstawia skład maszyn Turinga, który implementuje operator superpozycji dla n=1 i m=1.

Obrazek 1.

Definicja.

Iterację maszyny Turinga M będziemy nazywać maszyną

2. Operacja rozgałęziania.

Niech M 1, M 2 i M 3 będą maszynami Turinga posiadającymi ten sam alfabet zewnętrzny A« (a 0,a 1,...,a i,...,a j,...,a p) i odpowiednio zbiory stwierdza: Q1 " (q 0 ,q 1 ,...,q n ), Q2 " (q 0 " ,q 1 " ,...,q m " ), Q3 " (q 0 " , q 1 " ,.. .,ql").

Definicja.

Wynik operacji rozgałęzienia na maszynach Turinga M 1, M 2 i M3 nazywany jest maszyną Turinga M, której program otrzymuje się z programów maszyn M 1, M 2 i M 3 w następujący sposób: zapisana jest maszyna M1, następnie przypisane są programy maszyn M 2 i M 3. Jeżeli w stanie końcowym q 1 maszyny M1 zostanie zaobserwowany symbol a i, wówczas sterowanie zostanie przekazane maszynie M 2, tj. symbol q 1 zostaje zastąpiony przez symbol q 0" i maszyna M 2 rozpoczyna pracę. Jeżeli w stanie końcowym q 1 maszyny M 1 zostanie zaobserwowany symbol a j, to sterowanie zostaje przekazane maszynie M 3, czyli symbol q 1 zostaje zastąpiony symbolem q 0" i maszyna M 3 rozpoczyna pracę. Wszystkie pozostałe symbole w programach maszyn M 1 i M 2 pozostają niezmienione. Maszyna M kończy swoją pracę w stanie końcowym q 1 (w rezultacie pozostaje przeprowadzić całościowe przenumerowanie stanów maszyny M).

Wynik operacji rozgałęzienia na maszynach Turinga M 1, M 2 i M3 oznacza się następująco:

W przypadku dwuliterowych maszyn Turinga (maszyn Turinga z dwuliterowym alfabetem) operacja rozgałęzienia na dowolnych maszynach Turinga M1, M2 i M3 jest oznaczona w następujący sposób:

te. jeżeli podczas pracy maszyny M1 w stanie q 1 zostanie zaobserwowany symbol a 0, wówczas sterowanie zostanie przekazane maszynie M2, w przeciwnym wypadku – maszynie M3.

3. Operacja w pętli.

Niech M będzie maszyną Turinga z alfabetem A« (a 0 ,a 1 ,...,a p ) i zbiorem stanów Q« (q 0 ,q 1 ,...,q n ).

Definicja.

Wynik operacji zapętlenia nazwiemy maszyną Turinga, co oznaczymy wzorem (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2, 3,..., n)

którego program otrzymuje się z programu maszyny M przez zastąpienie symbolu q 1 w następstwie polecenia q i a j ®q 1 a t r, rО(L,R,L), t=0,1,2,.. .p, z symbolem q s .

2.4 Warianty maszyny Turinga

Model maszyny Turinga można rozszerzyć. Można rozpatrywać maszyny Turinga z dowolną liczbą taśm i taśmy wielowymiarowe z różnymi ograniczeniami. Jednak wszystkie te maszyny są kompletne w technologii Turinga i są modelowane przez zwykłą maszynę Turinga.

Jako przykład takiej równoważności rozważ redukcję dowolnego MT do MT działającego na półnieskończonej taśmie.

Twierdzenie: Dla każdej maszyny Turinga istnieje równoważna maszyna Turinga działająca na półnieskończonej taśmie.

Dowód:

Rozważmy dowód Yu.G.Karpova. Dowód tego twierdzenia jest konstruktywny, to znaczy podamy algorytm, za pomocą którego dla dowolnej maszyny Turinga można skonstruować równoważną maszynę Turinga o zadeklarowanej właściwości. Najpierw losowo numerujemy komórki taśmy roboczej MT, czyli ustalamy nowe miejsce informacji na taśmie:

Obrazek 1.

Następnie przenumerowujemy komórki i zakładamy, że symbol „*” nie występuje w słowniku MT:

Obrazek 1.

2.5 Obliczalność i rozstrzygalność Turinga

Powyżej udowodniono, że klasy funkcji obliczalnych za pomocą funkcji rekurencyjnych, maszyn Turinga lub normalnych algorytmów Markowa są zbieżne. Pozwala to uznać koncepcję „algorytmu obliczeniowego” za niezmienną w stosunku do metody opisu. Różnice obserwuje się jedynie w zastosowaniu obiektów algorytmicznych. Jeśli dla funkcji rekurencyjnych obiektami są liczby i funkcje numeryczne, a proces obliczeń określony jest przez operatory superpozycji, rekurencji, minimalizacji i iteracji, to dla maszyn Turinga takimi obiektami są symbole alfabetów pamięci zewnętrznej i wewnętrznej, a obliczenia proces jest określony protokołem wykorzystującym wyjście, przejście i poruszenie głową. W przypadku normalnego algorytmu Markowa takimi obiektami są słowa lub ciągi symboli, a proces obliczeniowy jest określony przez reguły podstawienia lub iloczyny, które zmieniają skład i strukturę pierwotnego ciągu symboli w pożądany wynik.

Funkcja arytmetyczna (numeryczna) to funkcja, której zakres wartości jest podzbiorem zbioru N, a jej dziedzina definicji jest elementem zbioru N.

W przypadku problemów algorytmicznych typową sytuacją jest znalezienie algorytmu do obliczenia funkcji numerycznej f(x 1, x 2, ..., x n), w zależności od całkowitych wartości argumentów x 1, x 2 , ..., x rz.

Funkcję f:N n →N nazywamy przeliczeniową, jeśli istnieje algorytm, który pozwala na dowolny zbiór wartości jej argumentów obliczyć wartość funkcji (lub wskazać, że funkcja nie jest zdefiniowana na danym zbiorze). Ponieważ definicja funkcji obliczeniowej opiera się na intuicyjnej koncepcji algorytmu, zamiast terminu „funkcja obliczeniowa” często używa się terminu „intuicyjna funkcja obliczeniowa”. Zatem problem masy ma rozwiązanie, jeśli funkcja arytmetyczna odpowiadająca temu problemowi jest intuicyjnie obliczalna.

Funkcję f(x 1 , x 2 , …, x n) nazywa się efektywnie obliczalną, jeśli dla danych wartości k 1 , k 2 , …, k n argumentów można znaleźć wartość funkcji f(k 1 , k 2 , …, k n) przy użyciu istniejącej procedury mechanicznej (algorytmu).

Zamiast wyjaśniać pojęcie algorytmu, możemy rozważyć wyjaśnienie pojęcia „funkcji obliczeniowej”. Zwykle postępują według następującego schematu:

1. Wprowadzono ściśle określoną klasę funkcji.

2. Upewnij się, że wszystkie funkcje tej klasy są obliczalne.

3. Przyjąć hipotezę (tezę), że klasa funkcji obliczalnych pokrywa się z wprowadzoną klasą funkcji.

Funkcję nazywa się obliczalną, jeśli istnieje algorytm, który ją oblicza. „Obliczalność” to jedno z podstawowych pojęć teorii algorytmów, niezmienne dla obliczanej funkcji i algorytmu. Różnica między funkcją obliczalną a algorytmem polega na różnicy między opisem funkcji a sposobem, w jaki oblicza ona jej wartości, biorąc pod uwagę wartości niezależnych argumentów.

Teza Turinga. Dowolny intuicyjny algorytm można zaimplementować na jakiejś maszynie Turinga.

Z tezy Turinga wynika, że ​​jeżeli pojawiają się problemy algorytmiczne, należy je rozwiązywać w oparciu o konstrukcję maszyn Turinga, czyli odpowiednio sformalizowaną koncepcję algorytmu. Co więcej, w problemach algorytmicznych często nie mówimy o konstruowaniu algorytmu, ale o obliczalności niektórych specjalnie skonstruowanych funkcji.

Należy zaznaczyć, że w takich przypadkach wystarczy użyć alfabetu (0,|), gdzie 0 jest znakiem pustym. Na przykład liczby naturalne, w tym 0, są kodowane w tym alfabecie w następujący sposób: 0 - |; 1 - ||; 2 -

N - ||…| (n + 1 razy). Częściowa numeryczna funkcja n-lokalna f(x1, x2, ..., xn) nazywana jest obliczalną Turinga, jeśli istnieje maszyna M, która oblicza ją w następującym sensie: 1. Jeśli zbiór wartości argumentów należy do dziedziny definicji funkcji f, wówczas maszyny M, rozpoczynającej pracę w konfiguracji 0 |x1+1 0 |x2+1 ... 0 |xn q1 |, gdzie |x = ||... | (x razy) i postrzegany jest znak znajdujący się najbardziej na prawo, zatrzymuje się, kończąc na konfiguracji 0|yq0 |, gdzie y = f(x1, x2, …, xn). 2. Jeśli zestaw wartości argumentów nie należy do dziedziny definicji funkcji f, to maszyna M rozpoczynając pracę w konfiguracji początkowej, pracuje w nieskończoność, czyli nie osiąga stanu końcowego. Maszyna Turinga to precyzyjna formalna definicja algorytmu. Stosując tę ​​koncepcję, można wykazać rozwiązywalność lub nierozwiązywalność problemów algorytmicznych. Jeśli okaże się, że algorytm obliczeniowy rozwiązuje problem należący do jednej klasy problemów, wówczas mówi się, że problem jest rozwiązalny algorytmicznie. Innymi słowy, warunkiem obliczalności lub efektywności obliczenia jest jego algorytmiczna rozwiązywalność. W tym sensie pojęcie „rozstrzygalności” jest także pojęciem podstawowym w teorii algorytmów. Analiza trzech typów modeli pokazuje, że podstawowe właściwości dyskretności, determinizmu, charakteru masowego i efektywności pozostają niezmienione dla różnych metod opisu: Własność dyskretności: algorytm składa się z pojedynczych elementarnych działań wykonywanych etapami; zbiór elementarnych kroków składających się na proces algorytmiczny jest skończony i policzalny. Właściwość deterministyczna: po każdym kroku podawane są dokładne instrukcje, jak i w jakiej kolejności wykonywać kolejne kroki procesu algorytmicznego. Własność masowa: zastosowanie algorytmu jest dopuszczalne dla wielu obiektów algorytmicznych danego typu i danej klasy problemów. Właściwość efektywności: zatrzymanie procesu algorytmicznego jest obowiązkowe po skończonej liczbie kroków wskazujących pożądany rezultat. Tezy jednak nie da się udowodnić, gdyż łączy ją ścisła koncepcja obliczalności Turinga z nieprecyzyjnym pojęciem funkcji intuicyjnie obliczalnej.

PROBLEM SAMOZASTOSOWANIA

Zgodnie z definicją maszyny Turinga jest to potrójność T= , w której A- alfabet, Q - stany wewnętrzne maszyny, Q- program odróżniający jedną maszynę od drugiej. W ogólnym przypadku (dla wszystkich maszyn) program może wyglądać np. tak:

P: q ja A j A ® q r A Jak A St A , a = 1, 2, …, k , Gdzie S 1- R, S2-L, S 3- C . (*)

W tym przypadku możemy założyć, że istnieją pewne wspólne alfabety 0 I Pytanie 0, w którym zapisywane są znaki A I Q dla wszystkich maszyn Turinga. Następnie symbole q ja A, j A, q r A, Jak A, St A są symbolami alfabetów 0 I Pytanie 0.

Podejście to pozwala na numerację wszystkich maszyn Turinga, to znaczy każdej maszynie przypisany jest określony numer (kod) unikalny dla tej maszyny, po którym można ją odróżnić od innych maszyn. Tutaj rozważymy jedną z metod numerowania.

Numeracja Godelowska maszyn Turinga. Pozwalać str. 1, str. 2, str. 3 , ... - ciąg liczb pierwszych ułożonych rosnąco, na przykład 2, 3, 5, 7, 11, 13, ...

Numer maszyny Turinga z programem (*) wywołany numer

n(T) = .

Przykład

Maszyna realizująca funkcję S(X)= x + 1 , ma program w alfabecie {0,  } . Numer tego programu, biorąc pod uwagę fakt, że 0 = 0 , 1= | będzie liczba:.

n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .

Oczywiście nie wszystkie liczby naturalne są liczbami maszyny Turinga. Z drugiej strony, jeśli N – numer danej maszyny, ogólnie w alfabecie, wówczas z tego numeru można jednoznacznie odtworzyć jej program.

Samochód T, odnoszące się do słowa N(T)(czyli na kod własnego numeru), zwane samozastosowawczym .

Możliwe jest zbudowanie zarówno maszyn samozastosowujących się, jak i maszyn niesamodzielnych. Przykładowo maszyna z podanego przykładu ma możliwość samodzielnego zastosowania. Samochód T, który nie ma symbolu stopu w odpowiednich częściach programu (w treści tabeli), nie ma zastosowania do żadnego słowa, a zatem do słowa N(T).

Problem samozastosowalności jest następująca: wskazać algorytm, który przy dowolnej maszynie Turinga określiłby, czy można go zastosować samodzielnie, czy nie.

Zgodnie z Tezą Turinga takiego algorytmu należy szukać w postaci maszyny Turinga. Maszyna ta powinna mieć zastosowanie do kodów liczbowych wszystkich maszyn Turinga i w zależności od wyniku przetwarzania kodów testowanych maszyn miałaby różne konfiguracje końcowe.

Weźmy na przykład ten samochód T zastosowane do kodu N(T * ) . Jeśli samochód T * do samodzielnego zastosowania, a następnie ostateczna konfiguracja maszyny T wygląda jak A" q 0 | B", a jeśli samochód T * nie nadaje się do samodzielnego zastosowania, wówczas ostateczna konfiguracja maszyny T wygląda jak A" q 0 0 B ". Tutaj a", B", a", B"- słowa.

Twierdzenie Problem samozastosowalności jest algorytmicznie nierozstrzygalny, to znaczy nie ma maszyny Turinga, która rozwiązałaby ten problem w powyższym sensie.

Z twierdzenia wynika, że ​​nie ma ogólnego algorytmu rozwiązującego problem samozastosowalności. W szczególnych przypadkach takie algorytmy mogą istnieć.

Wykorzystajmy wyniki tego twierdzenia, aby udowodnić nierozstrzygalność problemu stosowalności do słowa początkowego.

Problem stosowalności do słowa początkowego jest następująca: utwórz algorytm, który będzie zgodny z maszyną T i słowo X zainstalowałby odpowiednią maszynę T Przy okazji X czy nie (w przeciwnym razie wystąpi problem z zatrzymaniem).

W odniesieniu do maszyn Turinga, podobnie jak w przypadku sformułowania problemu samozastosowalności, problem ten jest sformułowany w następujący sposób: czy możliwe jest zbudowanie maszyny, która miałaby zastosowanie do wszystkich słów postaci N(T)0 X , Gdzie T dowolna maszyna, X – dowolne słowo, a jeśli maszyna T ma zastosowanie do słowa X A" q 0 |B" , a jeśli samochód T nie dotyczy słowa X , doprowadziłoby do ostatecznej konfiguracji A" q 0 0 B” . Tutaj a", B" I a", B"- dowolne słowa.

Twierdzenie Problem zastosowania do słowa początkowego jest algorytmicznie nierozstrzygalny, to znaczy nie ma maszyny Turinga, która rozwiązałaby ten problem w powyższym sensie.

Jak stwierdzono powyżej w przypadku problemu samodzielnego zastosowania, pierwszym wstępnym krokiem jest numeracja. Dlatego poniżej problem ten jest konsekwentnie rozpatrywany i rozwiązywany dla algorytmów i jego trzech głównych typów modeli algorytmicznych.


Numerowanie algorytmów

Numeracja algorytmów odgrywa ważną rolę w ich badaniach i analizach. Ponieważ dowolny algorytm można określić jako skończone słowo (reprezentowane jako skończona sekwencja symboli jakiegoś alfabetu), a zbiór wszystkich skończonych słów w skończonym alfabecie jest przeliczalny, wówczas zbiór wszystkich algorytmów jest również przeliczalny. Oznacza to istnienie odwzorowania jeden do jednego pomiędzy zbiorem liczb naturalnych a zbiorem algorytmów, czyli możliwość przypisania każdemu algorytmowi liczby.

Numeracja algorytmów to także numeracja wszystkich funkcji obliczalnych algorytmicznie, a każda funkcja może mieć nieskończoną liczbę liczb.

Istnienie numeracji pozwala pracować z algorytmami w taki sam sposób, jak z liczbami. Numerowanie jest szczególnie przydatne w badaniu algorytmów współpracujących z innymi algorytmami.

Niech istnieje pewien problem masy ze zbiorem obiektów początkowych X i zbiorem pożądanych obiektów Y. Aby istniało rozwiązanie problemu masy, konieczne jest, aby elementy zbiorów X i Y były obiektami konstrukcyjnymi. W związku z tym elementy tych zbiorów można ponumerować liczbami naturalnymi. Niech x∈ X będzie jakimś obiektem początkowym, oznaczmy jego numer przez n(x). Jeżeli w zagadnieniu masy dla pierwotnego obiektu x wymagane jest otrzymanie pożądanego obiektu y∈ Y o liczbie n(y), to definiujemy funkcję arytmetyczną f: Nn →N taką, że f(n(x))=n (y).

Jako przykład konstruowania funkcji arytmetycznych dla problemów masowych rozważmy problemy masowe.

1. Jeżeli dany jest zbiór ] liczb naturalnych, to można mu przypisać liczbę naturalną 2x1, 3x2,... p(n)xn, gdzie p(n) jest n-tą liczbą pierwszą. Weźmy przykład tablicy o długości 5:

] 2x13x25x37x411x5.

Ta numeracja definiuje funkcję arytmetyczną f (na przykład f(73500) = f(22315372110) = 20315272113 = 4891425).

2. Każda liczba wymierna ma jakąś liczbę naturalną. Numeracja zbioru wymaganych obiektów problemu jest banalna:

(„tak”, „nie”) a (1, 0). Dla danego problemu masy można skonstruować funkcję arytmetyczną jednego argumentu, korzystając z techniki z poprzedniego przykładu, lub można rozważyć funkcję trzech argumentów (trzy liczby elementów pierwotnej trójki).

3. Numerację tekstów programu można przeprowadzić następująco: dowolny program może być postrzegany jako zapisujący liczbę w systemie liczb 256-arytowych (jeżeli do zapisu programu użyto znaków tablicy ASCII).

Przejście od problemu masowego do funkcji arytmetycznej pozwala zredukować kwestię istnienia rozwiązania problemu masowego do kwestii istnienia skutecznego sposobu obliczenia wartości funkcji arytmetycznej na podstawie jej argumentu ( argumenty).

Numerowanie zbiorów liczb

W teorii algorytmów rozpowszechniła się technika, która pozwala sprowadzić badanie funkcji kilku zmiennych do badania funkcji jednej zmiennej. Opiera się na numeracji zbiorów liczb, tak aby istniała bijektywna zgodność między zbiorami liczb i ich liczbami, a funkcje określające ze zbioru liczb jego numer i z liczby sam zbiór liczb są na ogół rekurencyjne. Na przykład dla funkcji zawierającej dwie niezależne zmienne (x, y) to odwzorowanie h(x, y) mogłoby wyglądać następująco:

Obrazek 1.

Niech pary (x, y) tworzą częściowo uporządkowany zbiór N(2). Jeżeli dane jest h(x, y) = n, to następuje odwrotne odwzorowanie: x = h -1 1 (n) i y= h -1 2 (n), czyli h(h -1 1 (n), h -1 2 (n)) = n. Pozwala to obliczyć liczbę n dla dowolnej pary (x, y) i odwrotnie, używając liczby n do obliczenia wartości x i y:

Korzystając z tych reguł, możesz obliczyć numerację trójek h 2 (x, y, z) = h(h(x, y), z) = n i odwrotnie, według liczby trójek - wartości x, y, z. Na przykład, jeśli h 2 (x, y, z) = n, to z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h(h(h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n)) ) , h -1 2 (n)). Trójki (x, y, z) tworzą częściowo uporządkowany zbiór N(3). Podobnie dla dowolnej liczby liczb mamy:

h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Jeśli h n-1 (x1, x2,…, xn)=m, to xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m)), ... ...................................., x2 = h -1 2 (h -1 1 (. .. h -1 1 (m)...)), x1 = h -1 2 (h (...h (m)...)).

Mając numerację zbiorów zbiorów N (1) , N (2) ,..., N (i) ,..., N(n, gdzie N (i) jest zbiorem zbiorów (i) liczb, można ustalić łączną numerację dowolnych zbiorów liczb M = N (1) N (2) ... N (i) .. N(n) , gdzie M N. Dla dowolnego n N mamy h(x1, x2,..., xn )= h(h n −1 (x1,x2,..., xn), n −1).

Jeśli h(x ,1x ,2..., x)n = m, to h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Korzystając z powyższych wzorów, możesz przywrócić wartości x1, x2,…, xn.


Powiązana informacja.


Definicja, działanie i metody określania maszyny Turinga

Przez maszynę Turinga rozumie się pewną hipotetyczną (abstrakcyjną) maszynę składającą się z następujących części (ryc. 3.1.)

1) taśma nieskończona w obu kierunkach, podzielona na komórki, w których można zapisać tylko jeden znak z alfabetu oraz znak pusty l;

2) urządzenie sterujące (głowica robocza), które w dowolnym momencie może znajdować się w jednym ze stanów ze zbioru. W każdym stanie głowa jest umieszczona naprzeciwko komórki i może czytać (przeglądać) lub pisać do niej literę alfabetu A.


Ryż. 3.1. Maszyna Turinga

Funkcjonowanie MT składa się z ciągu elementarnych kroków (cykli). Każdy krok wykonuje następujące działania:

1. głowica robocza odczytuje (przegląda) symbol;

2. w zależności od jego stanu i monitorowanego symbolu głowica generuje symbol i zapisuje go do monitorowanej komórki (ewentualnie =) ;

3. głowa przesuwa się o jedną komórkę w prawo (R), lewy (L) lub pozostaje na miejscu (MI);

4. Głowa przechodzi w inny stan wewnętrzny. (prawdopodobnie =).

Stan nazywamy początkowym i końcowym. Po wejściu w stan końcowy maszyna zatrzymuje się.

Pełny stan MT nazywa się konfiguracja . Jest to rozkład liter pomiędzy komórkami taśmy, stan głowicy roboczej i monitorowanej komórki. Konfiguracja w takcie T jest zapisywane w postaci: , gdzie jest podsłowem po lewej stronie monitorowanej komórki, jest literą w monitorowanej komórce, jest podsłowem po prawej stronie.

Konfiguracja początkowa i konfiguracja końcowa nazywane są standardową.

Istnieją 3 sposoby opisania działania MT:

System poleceń formularza

Funkcjonalny stół;

Wykres (schemat) przejść.

Spójrzmy na nie na przykładach.

Przykład 1. Skonstruuj MT, który implementuje połączenie dwóch słów w alfabecie. Słowa na taśmie są oddzielone *. Początkowa konfiguracja jest standardowa.

System poleceń MT wygląda następująco:

W stanie głowa przesuwa się w prawo, aż do pustego symbolu.

Znak znajdujący się najbardziej na prawo zostanie usunięty.

Gwiazdka jest usuwana, jeśli pierwsze słowo jest puste.

Prawe słowo jest przesuwane znak po znaku w lewo o jedną pozycję.

Przejście do standardowej konfiguracji końcowej.

Tabela funkcji

A B * l
-
-
-
-

Kreski w tabeli oznaczają, że symbolu l nie można znaleźć w stanach.



a/aL b/bL
Schemat przejścia wygląda następująco:
a/aR b/bR */*R

Standardowa konfiguracja końcowa.

Obliczenie funkcji słownikowej na MT zrozumiemy w następujący sposób. Niech słowo a będzie zapisane na taśmie w początkowej konfiguracji. Jeśli wartość zostanie ustalona, ​​to po skończonej liczbie kroków (cykli) maszyna musi przejść do ostatecznej konfiguracji, w której słowo jest zapisywane na taśmie. W przeciwnym razie MT powinien działać w nieskończoność.

Za pomocą MT można opisać wykonywanie operacji arytmetycznych na liczbach. W tym przypadku liczby prezentowane są na taśmie jako słowa alfabetu składające się z liczb jakiegoś systemu liczbowego i oddzielone specjalnym znakiem nieuwzględnionym w tym alfabecie, np. *. Najpopularniejszym systemem jest system jednoargumentowy, składający się z pojedynczego symbolu –1. Liczba X na taśmie jest zapisana słowem (lub w skrócie) w alfabecie O=(1).

Funkcja numeryczna jest poprawnie obliczona (lub po prostu obliczona metodą Turinga), jeśli istnieje MT, która odwzorowuje konfigurację na konfigurację, gdy = y lub działa przez czas nieokreślony, jeśli jest niezdefiniowany.

Przykład 2. Operacja dodawania dwóch liczb w kodzie unarnym.

Konfiguracja wstępna:

Konfiguracja końcowa: tj. dodawanie tak naprawdę sprowadza się do przypisania liczby B do numeru A. W tym celu usuwa się pierwszą cyfrę 1, a * zastępuje cyfrą 1.

Podajemy opis MT w formie tabeli funkcjonalnej:

* l
-
-
-

Powyższe metody opisu MT można praktycznie zastosować jedynie w przypadku prostych algorytmów, gdyż w przypadku skomplikowanych opis staje się zbyt uciążliwy. Podobnie opisywanie funkcji rekurencyjnych przy użyciu jedynie najprostszych funkcji i operatorów superpozycji, prymitywnej rekurencji i minimalizacji byłoby niezwykle kłopotliwe. Dlatego pierwotną lub częściową rekursywność funkcji udowadnia się za pomocą innych funkcji, których pierwotna lub częściowa rekursywność została już udowodniona.

Podobnie maszyny Turinga obsługujące złożone algorytmy można zbudować przy użyciu istniejących maszyn MT. Konstrukcja ta nazywana jest kompozycją MT.

Opiszmy 4 główne metody składu MT:

Kompozycja sekwencyjna (superpozycja);

Kompozycja równoległa;

Rozgałęzianie

Kompozycja sekwencyjna maszyny i obliczanie funkcji słownikowych oraz w alfabecie A, zwany samochodem T, który oblicza funkcję. Kolejność kompozycji jest przedstawiona w następujący sposób:


i jest wyznaczony.

Skład sekwencyjny jest zwykle używany do opisu liniowych odcinków algorytmów.

Dowód twierdzenia o możliwości zbudowania maszyny T, który jest sekwencyjnym złożeniem dwóch dowolnych maszyn i odbywa się poprzez utożsamienie stanu końcowego ze stanem początkowym.

Przykład 3. Skonstruuj algorytm mnożenia 2*X w kodzie jednoargumentowym, korzystając z maszyny kopiującej, która tłumaczy słowo a na słowo a*a i maszyny dodającej. Wymagany MT wygląda następująco:

Kompozycja równoległa maszyny oraz obliczanie funkcji słownikowych i alfabetów A I W odpowiednio nazywa się maszynę T, który ocenia funkcję słownikową. Tutaj znak służy do oddzielania słów w równoległym składzie MT.

i jest oznaczony: .

W rzeczywistości równoległa kompozycja dwóch MT otrzymuje na wejściu słowo składające się z 2 słów w różnych alfabetach i wyprowadza słowo składające się z 2 słów, tj. reprezentuje dwie jednocześnie i niezależnie pracujące maszyny.

Aby wdrożyć kompozycję równoległą, stosuje się maszynę z dwupiętrowym pasem. Konieczność tego wynika z faktu, że obliczenia i czas następują sekwencyjnie, a obliczone na przykład najpierw mogą wymagać więcej miejsca niż a i zepsuć słowo b. Dwupiętrowa maszyna taśmowa działa w ten sposób: słowo b jest zapisywane na drugim piętrze i usuwane na pierwszym piętrze, obliczane na pierwszym piętrze, obliczane na drugim piętrze, a następnie przepisywane na pierwsze piętro, ewentualnie z przesunięciem .

Aby wdrożyć kompozycję równoległą N używane maszyny N- taśma podłogowa.

Polecenie MT z dwupiętrową taśmą jest napisane w następujący sposób: gdzie znajdują się litery zapisane odpowiednio na pierwszym i drugim piętrze.

Przykład 4. Zaimplementuj równoległy skład maszyn i funkcji obliczeniowych w systemie liczb binarnych i a+b w systemie unarnym.

Słowo wejściowe ma postać: .

Opiszmy działanie MT za pomocą systemu poleceń:

Przejdź w prawo do słowa b

Przepisanie słowa b na drugie piętro

Przejdź w lewo do słowa a

Dodanie 1 do liczby X.

Przejdź w prawo do słowa b.

Spis b do I piętra z jednoczesnym dodaniem liczb A I B.T odpowiednio. Polecenia w nawiasach klamrowych dodane do systemu poleceń

Stan końcowy całego MT.

Należy zaznaczyć, że we wszystkich przypadkach na początku algorytmu konieczne jest wstawienie sprawdzenia danych źródłowych pod kątem wartości specjalnych (najczęściej 0); niezastosowanie się do tego wymogu może doprowadzić do powstania pętli.

Kompozycję MT można wykorzystać do budowy złożonych algorytmów. Powstaje pytanie: czy dowolny algorytm można zaimplementować jako kompozycję MT? Odpowiedzi na to pytanie udziela Teza Turinga , analogia z tezą Churcha: każdy algorytm można zaimplementować na maszynach Turinga i odwrotnie, każdy proces realizowany na maszynie Turinga jest algorytmem.

Teza Turinga nie jest twierdzeniem; nie da się jej udowodnić, ponieważ zawiera nieformalną koncepcję „ algorytm" Jednak wieloletnia praktyka matematyczna jest rzetelnym potwierdzeniem tej tezy: od 50 lat nie znaleziono algorytmu w sensie intuicyjnym, którego nie dałoby się zaimplementować na maszynach Turinga.

Cel pracy: zdobyć praktyczne umiejętności pisania algorytmów z wykorzystaniem składu maszyn Turinga.

Informacje teoretyczne

Powyższe metody opisu MT można praktycznie zastosować tylko dla prostych algorytmów, w przeciwnym razie opis stanie się zbyt uciążliwy. Maszyny Turinga dla złożonych algorytmów można zbudować przy użyciu już istniejących elementarnych MT i taka konstrukcja nazywa się skład MT.

Opiszmy 4 główne metody składu MT:

Kompozycja sekwencyjna (superpozycja);

Kompozycja równoległa;

Rozgałęzianie

1. Układ sekwencyjny maszyn Turinga

Kompozycja sekwencyjna Lub nałożenie Maszyny Turinga i

I
w alfabecie A, to się nazywa samochód M, obliczenie funkcji
.

Kolejność kompozycji jest przedstawiona w następujący sposób:

i jest wyznaczony
Lub
.

2. Złożenie równoległe maszyn Turinga

Kompozycja równoległa samochody
I
, obliczanie funkcji słownikowych
I
w alfabetach A I W, odpowiednio nazywa się maszynę M, który ocenia funkcję słownikową. Oto znak używany do oddzielania słów w równoległym składzie MT.

Skład równoległy MT
I
jest przedstawiony w następujący sposób:

i jest oznaczony:
.

W rzeczywistości równoległa kompozycja dwóch MT otrzymuje na wejściu słowo składające się z 2 słów w różnych alfabetach i wyprowadza słowo również składające się z 2 słów, tj. reprezentuje dwie jednocześnie i niezależnie pracujące maszyny. Aby wdrożyć kompozycję równoległą, stosuje się maszynę z dwupiętrowym pasem.

Dwupoziomowa maszyna taśmowa działa w następujący sposób:

1) słowo przepisany na drugim piętrze taśmy i usunięty na pierwszym,

2) obliczone
na pierwszym piętrze,

3) obliczone
Na drugim piętrze

4)
przeniesiony na pierwsze piętro, ewentualnie z przesunięciem.

Polecenie MT z taśmą dwupoziomową zapisuje się w następujący sposób:

,

Gdzie
– listy pisane odpowiednio na pierwszym i drugim piętrze. Oznaczmy długości słów
odpowiednio,
.

Zademonstrujmy działanie maszyny Turinga na taśmie dwupiętrowej. Ogólnie rzecz biorąc, długości słów
I
nie pokrywają się ze sobą, ale dla uproszczenia obrazu zakładamy, że są sobie równe. Następnie realizacja punktów 1)-4) na MT za pomocą dwupiętrowej taśmy odbywa się w następujący sposób:

Aby wdrożyć kompozycję równoległą N Stosowane są maszyny Turinga N– taśma podłogowa.

3. Rozgałęzienie lub przejście warunkowe w kompozycjach maszyn Turinga

Jeśli dane są maszyny Turinga
I
, obliczanie funkcji słownikowych
I
i samochód
, który ocenia jakiś predykat P() z przywróceniem (tj. bez wymazywania słowa ), wówczas można zbudować maszynę Turinga do realizacji rozgałęzień
, obliczając funkcję:

Rozgałęzienie maszyn Turinga na diagramach kompozycji przedstawiono w następujący sposób:

i jest wyznaczony
, Tutaj
- wynik pracy maszyny
, przyjmując wartości „1” w przypadku predykatu P()= ”PRAWDA” i „0”, jeśli predykat P()= “FAŁSZ” ,
– maszyna Turinga realizująca kopiowanie słowa wejściowego
.

4 . Cykl w składzie maszyn Turinga

Cykl w składzie MT jest realizowany według tych samych zasad, co rozgałęzianie.

" Do widzenia P()= ”PRAWDA” , spełnić
»,

Gdzie – słowo na taśmie przed pierwszym wykonaniem
i po kolejnej egzekucji .

Dla zobrazowania cyklu wprowadzimy pewną notację, niech:

– maszyna Turinga realizująca obliczenia predykatu P() ;

–MT, który implementuje kopiowanie słowa wejściowego
;

–MT, wykonywane w pętli i implementujące
;

–MT, wykonywane przy wyjściu z pętli i implementowaniu
.

Następnie cykliczną kompozycję maszyn Turinga, czyli cykl, można przedstawić w następujący sposób:

Programowanie przy użyciu kompozycji na maszynie Turinga:

1) konstruowanie schematów blokowych złożonych algorytmów o takim stopniu szczegółowości, aby ich bloki odpowiadały elementarnemu MT;

2) budowa elementarnych MT realizujących proste bloki;

3) łączenie elementarnych MT w kompozycję MT.

Przykład. Zbuduj kompozycję MT, która implementuje
.

–Maszyna Turinga, która realizuje kopiowanie słowa wejściowego;

–MT, który realizuje funkcję ustawienia stałego zera;

–MT, predykat obliczeniowy z przywracaniem
;

– MT realizujący funkcję selekcji -ten argument z argumenty;

–MT, implementująca funkcję redukcji argumentów o 1 w kodzie jednoargumentowym (usuwa znak skrajnie lewy);

– MT, który wykonuje dodanie dwóch liczb w kodzie unarnym.

Należy zaznaczyć, że w każdym przypadku konieczne jest sprawdzenie poprawności danych wejściowych już na początku wykonywania algorytmu (np. zgodność argumentu z 0 podczas dzielenia).

Rysunek 1.6

Na rysunku 1.6 zastosowano następujące oznaczenia:

T 1, T 2 - Maszyny Turinga;

ST 1, ST 2 - systemy dowodzenia odpowiednio maszynami T 1 i T 2;

x - informacja wstępna dla maszyny T 1;

T 1 (x) - wynik działania maszyny T 1;

T 2 (T 1 (x)) - wynik działania maszyny T 2.

Jako przykład rozważmy złożenie dwóch maszyn, z których pierwsza wykonuje operację kopiowania, a druga operację dodawania liczb w kodzie jednoargumentowym. Schemat połączenia maszyn oraz przykład taśmy z uzyskanymi wynikami pokazano na rysunku 1.7.


Rysunek 1.7

Kompozycja pokazana na rysunku 1.7 pozwala na wykonanie operacji podwojenia liczby przy użyciu znanych już maszyn kopiujących i dodających. Zatem po skomponowaniu algorytmów dla maszyn Turinga w celu rozwiązania zestawu określonych operacji (na przykład operacji arytmetycznych) można następnie skomponować kompozycje maszyn Turinga w celu rozwiązania bardziej złożonych problemów. W tym przypadku opracowanie algorytmu ogólnego sprowadza się do jego kompilacji z tych operacji, dla których znane są już algorytmy wykonania na maszynie Turinga. Podejście to przypomina wykorzystanie procedur i funkcji w programowaniu.

Jednakże zastosowanie składu maszynowego zakłada, że ​​znane są algorytmy wykonywania operacji elementarnych, z których składa się algorytm ogólny. Dlatego przy rozwiązywaniu dowolnych problemów takie podejście nie wyklucza konieczności komponowania nowych algorytmów i, w związku z tym, opracowywania maszyn Turinga z różnymi jednostkami sterującymi. Możliwe jest zaimplementowanie dowolnego algorytmu bez zmiany struktury jednostki sterującej przy użyciu uniwersalnej maszyny Turinga.



1.2.2.Uniwersalna maszyna Turinga

Jeśli podana jest jakaś maszyna Turinga (tj. znane są alfabety sygnałów wejściowych, wyjściowych i stanów, początkowe położenie głowicy i stan początkowy maszyny, a także tabela działania maszyny i taśma z informacjami początkowymi) ), wówczas wszystkie przekształcenia informacji można wykonać ręcznie krok po kroku, do czego ta maszyna jest przeznaczona. W rzeczywistości w tym przypadku przeprowadzana jest symulacja maszyny Turinga.

Analizując operacje jakie są wykonywane przy modelowaniu maszyny Turinga można stwierdzić, że modelowanie sprowadza się do powtarzania w każdym kroku następujących czynności:

ĘOdczyt znaku z komórki taśmy, nad którą znajduje się głowica.

ĘWyszukaj polecenie w tabeli obsługi maszyny. Wyszukiwanie odbywa się na podstawie aktualnego stanu maszyny i wartości odczytanego symbolu.

ĘWybranie symbolu z polecenia, które ma zostać zapisane na taśmie i nagranie go.

ĘWybierz z polecenia symbol ruchu głowy i przesuń go.

ĘWybór nowego stanu maszyny z polecenia i zmiana aktualnego stanu na nowy. Następnie następuje przejście do następnego kroku i powtarzanie tych kroków.

ST
SU

Rysunek 1.8

Charakter tych elementarnych działań jest taki, że wszystkie można wykonać na jakiejś innej maszynie Turinga, która będzie symulować działanie oryginalnej maszyny. Istotę modelowania objaśniono na rysunku 1.8.

Jeżeli maszyna T posiada system poleceń ST i przetwarza taśmę z informacją X, to jej działanie może być symulowane przez inną maszynę U, która posiada własny system poleceń SU. Aby zasymulować wejście maszyny U, należy przesłać nie tylko taśmę z informacją X , ale także system dowodzenia (stół roboczy) ST. Ten system poleceń można nagrać na tej samej taśmie, co informacje oryginalne.

Rysunek 1.9

Ważną cechą maszyny symulującej jest to, że jej system dowodzenia SU (i odpowiednio struktura jednostki sterującej) nie jest zależny od algorytmu działania symulowanej maszyny T. Maszyna Turinga, która może symulować działanie dowolnej innej maszyny Turinga maszyna nazywa się uniwersalna. Wariant budowy uniwersalnej maszyny Turinga (UMT) pokazano na rysunku 1.9.

Taśma UMT jest podzielona na trzy strefy: strefę danych, strefę trybu i strefę poleceń.

Strefa danych zawiera początkowe informacje, które muszą zostać przetworzone przez symulowaną maszynę Turinga. W tej samej strefie rejestrowane są wyniki operacji UMT.

Strefa modowa rejestruje aktualny stan Qt oraz aktualny symbol wejściowy Xt, który jest odczytywany z komórki strefy danych w danym cyklu.

Strefa poleceń zawiera system dowodzenia symulowanej maszyny. Polecenia są podzielone na grupy. Do pierwszej grupy zaliczają się polecenia zaczynające się od symbolu Q 0, do drugiej – od symbolu Q 1 itd. W każdej grupie polecenia uporządkowane są według wartości symbolu X t . Zatem polecenia na taśmie znajdują się tak, jak znajdują się w tabeli operacyjnej symulowanej maszyny.

Odczyt informacji z taśmy i zapis na taśmę realizowane są za pomocą trzech głowic: G d - głowica danych, G r - głowica trybu, G k - głowica poleceń. Każda głowica może poruszać się po własnej strefie pasa.

Zanim UMT zacznie działać, w każdej strefie taśmy należy zapisać odpowiednią informację. Głowice należy zamontować nad lewym symbolem w każdej strefie.

Działanie UMT odbywa się cyklicznie, w każdym cyklu symulowane jest wykonanie jednego polecenia symulowanej maszyny. Wykres działania UMT przedstawiono na rysunku 1.10.


Rysunek 1.10

Na rysunku 1.10 zastosowano następujące oznaczenia:

Q G do P (G do L, G r P, G r L, G d P, G d L) - przesuwanie jednej z głów

prawo czy lewo;

Q (G k), (G d), (G r) - informacja odczytana przez jednego z szefów;

Q (G k) à (G r) - odczyt danych przez komendę i zapis tych danych

przeniesiony za pomocą głowicy trybu do strefy trybu taśmy;

Q a jest zmienną pomocniczą, która przyjmuje wartość 1, es-

czy znaki czytane przez główki Гк i Гр pokrywają się;

Q in jest zmienną pomocniczą, która przyjmuje wartość 1, es-

czy symbole stanu bieżącego (Q t) i końcowego (Q z).

Q p - sygnał, który przyjmuje wartość 1, jeśli komenda jest wysyłana

ruch w lewo przekroczył granice strefy dowodzenia;

W każdym cyklu pracy UMT wykonywane są następujące kroki:

szukasz strefy dowodzenia;

szukasz drużyny w strefie;

u symulacja wykonania polecenia.

Poszukiwanie strefy dowodzenia rozpoczyna się od porównania aktualnego stanu Q t ze strefy trybu ze stanem Q i zarejestrowanym na początku pierwszego polecenia w strefie dowodzenia. Jeżeli stany te nie są równe, wówczas głowica komendy przechodzi na początek kolejnej komendy, dla której wykonuje się pięć kroków głowicy w prawo (stany U 0 – U 4). Jeśli symbole Q t i Q i są zgodne, głowica dowodzenia znajduje się na początku pierwszego polecenia żądanej strefy. Następnie rozpoczyna się wyszukiwanie polecenia odpowiadającego symbolom Qt i Xt strefy trybu. W tym celu głowicę trybu umieszcza się nad symbolem X t strefy trybu, a głowicę komend umieszcza się nad symbolem X i w bieżącym poleceniu.

Wyszukiwanie polecenia w strefie jest podobne do wyszukiwania strefy dowodzenia. W tym przypadku komenda przesuwa się o pięć kroków w prawo (stany U 5 - U 9), aż do momentu porównania znaków X t i X i.

Wykonanie polecenia (stany U 10 - U 17) rozpoczyna się od przesunięcia głowicy komendy o jeden krok w prawo, po czym symbol Y t ​​​​odczytany ze znalezionego polecenia zostaje zapisany do strefy danych przy użyciu głowicy danych zamiast przeczytaj wcześniej symbol X t . Po kolejnym kroku głowicy rozkazów w prawo, ze znalezionego polecenia odczytywany jest symbol przesuwania głowicy danych (Y d) i głowica danych przesuwana jest zgodnie z tym symbolem (R, L). Poniżej znajduje się kolejny przetworzony symbol (X t +1), który za pomocą głowicy trybu jest zapisywany do strefy trybu w celu przygotowania kolejnego cyklu. Następnie instalowane są głowice poleceń i trybów, aby następny stan Q t +1 (stany

U 14, U 15). W stanie U 16 sprawdzany jest warunek zakończenia rozwiązania. Jeżeli symbol kolejnego stanu nie pokrywa się z symbolem stanu końcowego modelowanej maszyny (Q z), to rozwiązanie problemu nie jest zakończone, a w stanie U 17 głowica dowodzenia powraca do swojego pierwotnego położenia ( do początku pierwszego polecenia pierwszej strefy). W tym przypadku UMT jest gotowy do wykonania kolejnego cyklu, tj. symulować wykonanie następnego polecenia.

Kiedy symbole Q t i Q z pokrywają się, rozwiązanie problemu kończy się i UMT przechodzi do stanu końcowego U z .

Analizując proces działania UMT można wyciągnąć istotny wniosek, że algorytm działania UMT nie jest zależny od tego, jaki konkretny problem rozwiązuje symulowana maszyna Turinga. Dlatego struktura jednostki sterującej UMT nie zmienia się podczas modelowania różnych maszyn, tj. nie zależy od rozwiązywanych zadań. Dlatego UMT jest naprawdę uniwersalną maszyną, za pomocą której można wykonać dowolny algorytm bez zmiany jego struktury.

Ponieważ proces wyboru kolejnego polecenia UMT i jego wykonanie wiąże się z sekwencyjnym wyliczaniem komórek taśmy, rozwiązywanie problemów na UMT zajmuje zbyt dużo czasu. Dlatego nigdy nie zbudowano maszyny Turinga, w tym także uniwersalnej, ale nietrudno dopatrzeć się w niej analogii współczesnych komputerów. Zatem system poleceń w strefie poleceń UMT jest podobny do programu maszynowego, w którym para symboli Q t i X t pełni rolę adresu polecenia maszynowego.

Jednak maszyna Turinga jest dość wygodnym sposobem opisu algorytmów i jest szeroko stosowana w teorii algorytmów.

Pytania kontrolne

ü1.Jaki jest skład maszyn Turinga?

ü2. Do czego służy skład maszyn Turinga?

ü3.Czy jedna maszyna Turinga może symulować działanie innej maszyny?

Turinga?

ü4. Jakie działania są wykonywane w tym przypadku?

ü5.Wyjaśnij budowę uniwersalnej maszyny Turinga?

ü6.Jakie informacje są zapisane w obszarach taśmy UMT?

ü7.Jaki jest system dowodzenia maszyny Turinga?

ü8. Z jakich etapów składa się cykl pracy UMT?

ü9.Wyjaśnij zawartość kroku „szukaj strefy dowodzenia”.

ü10. Wyjaśnij treść kroku „wykonanie polecenia”.

ü11.Z jakich cech korzysta proces przetwarzania informacji

Diagram wygląda jak wykres:

Wartość tabeli maszyny

Tabela 1

  1. Niektóre operacje na maszynach Turinga

Działanie maszyny Turinga jest całkowicie zdeterminowane danymi wejściowymi i systemem poleceń. Jednakże, aby zrozumieć, jak dana maszyna rozwiązuje problem, z reguły potrzebne są sensowne wyjaśnienia tego typu, jakie zostały podane dla maszyny . Wyjaśnienia te często można uczynić bardziej formalnymi i precyzyjnymi, korzystając ze schematów blokowych i niektórych operacji na maszynie Turinga. Przypomnijmy, że złożenie funkcji
I
zwaną funkcją
, który uzyskuje się podczas używania do wyniku obliczeń . W celu
był na to zdecydowany , jest to konieczne i wystarczające ustalono na
, A ustalono na .

Twierdzenie 1. Jeśli
I
są obliczalne metodą Turinga, a następnie ich skład
jest również obliczalna metodą Turinga.

Pozwalać - maszyna, która liczy , A - maszyna, która liczy i odpowiednio zbiór ich stanów
I
.

Zbudujmy diagram przejścia samochodu ze schematów I w następujący sposób: identyfikujemy wierzchołek początkowy
schematy maszyn z wierzchołkiem końcowym
schematy maszyn (w przypadku systemów dowodzenia jest to równoznaczne z faktem, że system dowodzenia przypisany do systemu dowodzenia i za to
w drużynach zamienić
). Otrzymujemy diagram z (
) stwierdza. Stan początkowy ogłosimy
i ostateczne
. Dla uproszczenia zapisu założymy I funkcje numeryczne jednej zmiennej.

Pozwalać
określony. Następnie
I

. Samochód przejdzie przez tę samą sekwencję konfiguracji z tą różnicą, że zamiast
odbędzie się w
. Ta konfiguracja jest standardową konfiguracją początkową maszyny , Dlatego
. Ale ponieważ wszystkie zespoły zawarte w , To

i dlatego
. Jeśli
nie jest zatem zdefiniowane Lub nie zatrzymuje się i dlatego samochód nie przestanie. Więc samochód oblicza
.

Tak zbudowana maszyna nazwiemy to kompozycją maszyn I i wyznaczyć
(Lub ()), a także przedstawiono na schemacie blokowym:

  1. Skład maszyn Turinga

Pozwalać ,,- trzy maszyny Turinga z tym samym zewnętrznym alfabetem
, z alfabetami stanów wewnętrznych
,
,
i programy ,
,
odpowiednio.

Kompozycja
samochody I zwany samochódT , którego programem jest suma zbiorów
I

, Gdzie
oznacza zestaw poleceń otrzymanych od wymieniając wszystko NA .

  1. Odgałęzienie maszyn Turinga

Maszyny rozgałęziające,,Przez
, symbolicznie

zwany samochódT , którego program uzyskuje się w następujący sposób: z drużyny są wykluczone
I
Dla
, wywołany zostanie wynikowy zestaw ; Następnie.

  1. Uniwersalna maszyna Turinga

System dowodzenia maszyny Turinga można interpretować zarówno jako opis działania konkretnego urządzenia, jak i jako program, tj. zestaw instrukcji, które wyraźnie prowadzą do wyniku. Analizując przykłady, mimowolnie przyjmuje się drugą interpretację, tj. działamy jak mechanizm, który może odtworzyć pracę dowolnej maszyny Turinga. Pewność, że każdy zrobi to w ten sam sposób (o ile nie popełni błędów, co notabene zakłada się również przy działaniu maszyny Turinga) jest w istocie pewnością pewnością w istnieniu algorytmu odtwarzającego działanie maszyny Turinga maszynę według zadanego programu, tj. system dowodzenia. Rzeczywiście nie jest trudno podać słowny opis takiego algorytmu. Jego główna akcja jest powtarzana cyklicznie i składa się z następujących czynności: „Dla bieżącej konfiguracji
znajdź polecenie po lewej stronie w systemie poleceń
. Jeśli prawa strona tego polecenia ma postać
, a następnie zastąp w bieżącej konfiguracji
NA
(okazuje się, że konfiguracja
); jeśli prawa strona ma postać
, a następnie wymień
NA
. Ustny opis algorytmu może być niedokładny i wymaga sformalizowania. Ponieważ obecnie rozważana jest maszyna Turinga jako taka formalizacja koncepcji algorytmu, naturalnym jest postawienie problemu zbudowania maszyny Turinga realizującej opisywany algorytm reprodukcji. Dla maszyn Turinga, które obliczają funkcje jednej zmiennej, sformułowanie tego problemu jest następujące: zbuduj maszynę Turinga , obliczając funkcję dwóch zmiennych i taką, że dla dowolnej maszyny z systemem dowodzenia
, Jeśli
zdefiniowany (tj. jeśli maszyna zatrzymuje się na danych początkowych ) I
nie kończy się, jeśli
nie zatrzymuje się. Wywołamy dowolną maszynę, która ma tę właściwość uniwersalna maszyna Turinga. Uogólnienie tego sformułowania na dowolną liczbę zmiennych nie jest trudne.

Pierwszy problem, który pojawia się przy budowie maszyny uniwersalnej , wynika z tego, że jak każda inna maszyna Turinga, musi mieć ustalony alfabet
i ustalony zbiór stanów
. Dlatego system dowodzenia
oraz początkowe dane dowolnej maszyny nie można go po prostu przenieść na pasek maszyny (zawsze jest samochód , alfabety
I
który ma większą moc
I
lub po prostu z nim nie pokrywają się).

Rozwiązaniem jest posiadanie postaci z
I
zakodowane za pomocą symboli alfabetu
. Pozwalać
,
. Zawsze będziemy tak zakładać
I
(te dwa symbole są zawsze zapisane w alfabecie dowolnej maszyny obsługującej liczby). Oznaczmy kody I Poprzez
I
i zdefiniuj je jako
; dla kogokolwiek innego
; dla stanu końcowego


, Jeśli

. Kod
dla tego samochodu zawsze ma długość (format)
i kod
-format . Symbolika ,
wejdźmy
, tj.
,
,
. Kod znaku , utworzone przez kody znaków tworzących to słowo, oznaczamy
. Tym samym ostateczne udoskonalenie sformułowania problemu maszyny uniwersalnej sprowadza się do tego, że dla każdego samochodu i słowa alfabet
.

Istnienie uniwersalnej maszyny Turinga oznacza, że ​​system instrukcji
jakikolwiek samochód można interpretować dwojako: albo jako opis działania oryginalnego urządzenia lub jako program dla maszyny uniwersalnej . Dla współczesnego inżyniera projektującego układ sterowania jest to okoliczność naturalna. Dobrze wie, że dowolny algorytm sterowania można zaimplementować albo sprzętowo – budując odpowiedni układ, albo programowo – pisząc uniwersalny program komputerowy sterujący.

Należy jednak zdać sobie sprawę, że idea uniwersalnego urządzenia algorytmicznego jest całkowicie niezwiązana z rozwojem nowoczesnych środków technicznych jego realizacji (elektronika, fizyka ciała stałego itp.) i nie jest faktem technicznym, ale matematycznym , opisane w abstrakcyjnych terminach matematycznych, niezależnych od środków technicznych, a ponadto oparte na niezwykle małej liczbie bardzo elementarnych pojęć początkowych. Charakterystyczne jest, że podstawowe prace z teorii algorytmów (w szczególności dzieło Turinga) pojawiły się w latach 30. XX wieku, przed powstaniem współczesnych komputerów.

Ta podwójna interpretacja zachowuje na poziomie abstrakcyjnym główne zalety i wady dwóch opcji wdrożenia inżynieryjnego. Konkretny samochód działa znacznie szybciej; ponadto urządzenie sterujące maszyny dość uciążliwy (tj. liczba stanów i poleceń jest duża). Jednak jego wartość jest stała i po skonstruowaniu nadaje się do implementowania dowolnie dużych algorytmów. Wystarczy duża ilość taśmy, która jest oczywiście uważana za tańszą i prostszą w konstrukcji niż urządzenie sterujące. Ponadto przy zmianie algorytmu nie będzie potrzeby budowania nowych urządzeń, wystarczy napisać nowy program.