Algorytmiczne maszyny do prezentacji. Maszyna Turinga

Opracowanie metodologiczne lekcji, które zostanie omówione w tej publikacji, jest przeznaczone do nauki w klasie 10 przy rozważaniu bloku tematycznego ” Algorytm. Wykonawcy algorytmów».

W lekcji na ten temat ” »W towarzystwie prezentacji multimedialnej dzieci zapoznają się z jej budową, poznają zasadę działania oraz nauczą się budować program dla maszyny Turinga. Materiał lekcji pozwala rozwijać myślenie algorytmiczne uczniów szkół ponadgimnazjalnych, umiejętność formalizowania.

Według rodzaju ta lekcja jest połączona, w której badanie nowego materiału jest konsolidowane w procesie rozwiązywania problemów na ten temat. Autor opracowania proponuje zastosowanie metody częściowego poszukiwania nauczania, gdy proces myślenia staje się produktywny przy konsekwentnym ukierunkowaniu i kontroli nauczyciela.

Opis przebiegu lekcji o maszynie Turinga

Na etapie organizacji zajęć nauczyciel przygotowuje dzieci do pracy, formułuje temat lekcji oraz opowiada o angielskim Alanie Turingu, który znacząco wpłynął na rozwój informatyki jako nauki.

Na rozgrzewkę w kolejnym etapie lekcji decydują uczniowie logiczne zadanie po czym następuje czek na tablicy. Ważne jest, aby zwrócić uwagę na umiejętność sporządzenia algorytmu rozumowania.

Po zajęciu się rozgrzewką aktualizujemy poprzednio przebyte materiał teoretyczny o algorytmie i wykonawcach algorytmów. W tym celu autor opracowania proponuje przeprowadzenie frontalnej ankiety na następujące pytania:

Co nazywa się algorytmem i dla kogo jest przeznaczony?

Jakie właściwości ma algorytm?

Kto może występować jako wykonawca algorytmu?

Jakie są podstawowe koncepcje maszyny Turinga?

Zademonstruj główne właściwości algorytmów na przykładzie maszyny Turinga.

Przykłady maszyn Turinga - część teoretyczna

Przed przystąpieniem do rozwiązywania problemów na ten temat, w części teoretycznej podajemy opis maszyny Turinga. Zwracamy uwagę klasy na dwa elementy każdej z tych maszyn:

1) taśma jest nieograniczona i podzielona na komórki;
2) sterowana programowo głowica odczytująca informacje i nazywana automatem.

Zastąp jedną literę alfabetu zawartą w widocznej komórce pamięci inną;

Przesuń się w prawo lub w lewo w odstępie jednej komórki lub pozostań w tym samym miejscu;

Zmień swój stan wewnętrzny.

Rozwiązywanie problemów za pomocą maszyn Turinga

Kolejny etap lekcji polega na zanurzeniu się w praktycznej części lekcji i rozwiązywaniu problemów na dany temat. Nauczyciel mówi, że za pomocą maszyny Turinga należy spróbować zasymulować urządzenie podobne do kalkulatora. W sumie proponowane są dwa zadania, których analiza odbywa się wraz ze slajdami prezentacji:

Cel 1. Taśma maszyny Turinga zawiera pewną liczbę dziesiętną. Do tego należy dodać 1 ( jednostka). Automat w tym przypadku sprawdza pewną cyfrę odpowiadającą numerowi wejściowemu.

Definicja maszyny Turinga

Maszyna Turinga jest abstrakcyjnym wykonawcą, który implementuje proces algorytmiczny zaprojektowany w celu udoskonalenia koncepcji algorytmu. Jest to obiekt matematyczny, a nie fizyczna maszyna. Zaproponowana przez Alana Turinga w 1936 roku maszyna Turinga jest rygorystyczną konstrukcją matematyczną, aparatem matematycznym przeznaczonym do rozwiązywania pewnych problemów.

Budowa i opis maszyny Turinga Maszyna Turinga składa się z: taśmy bez końca podzielonej na komórki; karetka (głowica do czytania i pisania); programowalna maszyna (program w formie tabeli). Maszyna „widzi” za każdym razem tylko jedną komórkę. W zależności od tego, jaką literę widzi, a także w zależności od stanu q, automat może wykonać następujące czynności: napisać nową literę do obserwowanej komórki; wykonaj przesunięcie wzdłuż taśmy o jedną komórkę w prawo / w lewo lub pozostań w bezruchu; przejść do nowego stanu.

1) Alfabet zewnętrzny A = (a 0, a 1, ..., a n) Element a 0 nazywamy pustym symbolem lub pustą literą (znak, że komórka jest pusta). W alfabecie tym oryginalny zbiór danych i wynik algorytmu są zakodowane w postaci słowa. Struktura maszyny Turinga

2) Alfabet wewnętrzny Q = (q 0, q 1,…, qm), (P, L, N!) W dowolnym momencie maszyna Turinga znajduje się w jednym ze stanów q 0, q 1,…, qm In w tym przypadku: q 1 - stan początkowy (maszyna rozpoczyna pracę) q 0 - stan końcowy (maszyna zakończyła pracę) Symbole (P, L, N!) - symbole przesunięć (prawo, lewo, w miejscu) Budowa maszyny Turinga

Rodzaje poleceń maszyny Turinga Napisz nową literę do obserwowanej komórki Przesuń wzdłuż taśmy o jedną komórkę w prawo/lewo lub pozostań w miejscu (P, L, N) Przejdź do nowego stanu. a 0 a 1… a i… a j q 0 q 1… a k (LPN) q m q i… q j 1 1 1 * 1 1 Wskazanie zmiany symbolu Wskazanie przesunięcia karetki Wskazanie zmiany stanu wewnętrznego

3) Pamięć zewnętrzna (taśma) Maszyna posiada taśmę podzieloną na komórki, z których każda może zawierać tylko jedną literę Budowa maszyny Turinga

3) Pamięć zewnętrzna (taśma) Struktura maszyny Turinga Pusta komórka zawiera 0. W każdym momencie na taśmie zapisywana jest skończona liczba niepustych liter.Taśma jest skończona, ale w każdej chwili jest uzupełniana komórkami po lewej i prawej stronie, aby zapisać nowe niepuste znaki. Jest to zgodne z zasadą abstrakcji potencjalnej wykonalności

4) Karetka (głowica kontrolna) Karetka maszyny znajduje się nad pewną komórką taśmy - rozpoznaje znak zapisany w komórce. W jednym cyklu pracy karetka jest przesunięta o jedną komórkę (w prawo, w lewo) lub pozostaje Urządzenie maszyny Turinga

5) Schemat funkcjonalny (program) Program maszyny składa się z instrukcji: Budowa maszyny Turinga Dla każdej pary (q i, a j) program maszyny musi zawierać jedną instrukcję (deterministyczna maszyna Turinga)

Na początku działania maszyny początkowy zestaw danych jest podawany na taśmę w postaci słowa  Opis działania maszyny Turinga Powiemy, że niepuste słowo  w alfabecie A \ (a 0) jest odbierane przez maszynę w swojej standardowej pozycji, jeśli: - jest podane w kolejnych komórkach taśmy, - wszystkie pozostałe komórki są puste - samochód patrzy na skrajną prawą komórkę z tych, które zawierają słowo 

Opis działania maszyny Turinga Pozycja standardowa nazywana jest pozycją początkową (końcową), jeśli maszyna odbierająca słowo w pozycji standardowej jest w stanie początkowym q 1 (stan zatrzymania q 0)

Będąc w stanie nie-końcowym maszyna wykonuje krok, który jest określany przez aktualny stan q i oraz monitorowany symbol a j Opis działania maszyny Turinga

Opis działania maszyny Turinga Zgodnie z poleceniem qiaj  qkal X wykonywane są następujące czynności: 1) Zawartość obserwowanej komórki aj jest kasowana i zapisywany jest w niej symbol al (który może pokrywać się z aj) 2) Maszyna wchodzi w nowy stan qk (może pokrywać się ze stanem qi) 3) Karetka porusza się zgodnie ze sterowanym znakiem X  (P, L, N!)

Gdy maszyna wejdzie w stan końcowy q 0, jej działanie zostaje zatrzymane Taśma zawiera wynik działania algorytmu - słowo  w alfabecie A \ (a 0) Opis działania maszyny Turinga

Słowo maszynowe (konfiguracja) maszyny Turinga to słowo o postaci  1 q k a l  2, gdzie  1 i  2 to słowa w alfabecie A.

Konfiguracja  1 q k a l  2 jest interpretowana następująco: - maszyna jest w stanie q k - karetka patrzy na symbol a l na taśmie -  1 i  2 to zawartość taśmy przed i po symbolu a l

Sytuacje niestosowalności maszyny Turinga Uważa się, że maszyna Turinga nie ma zastosowania do danego słowa wejściowego, jeśli w programie nie ma komórek stopu lub maszyna nie uderza w nie podczas pracy. Na przykład: Maszyna Turinga ma zastosowanie do danego słowa wejściowego, jeśli po rozpoczęciu pracy nad tym słowem wejściowym prędzej czy później dotrze do jednej z komórek zatrzymujących. Jak zmienił się przykładowy program? a 0 0 1 q 1 1P q 1 0P q 1 1P q 1 a 0 0 1 q 1 1H q 0 0P q 1 1P q 1

Przykład maszyny Turinga Zbudowanie maszyny Turinga jest wymagane do rozwiązania następującego problemu: w słowie wejściowym zastąp wszystkie litery „a” literami „b” i odwrotnie. a 0 a b c ... i q 1 a 0 H! b L q 1 a L q 1 c L q 1 ... i L q 1 y  y b  a a  b r  r u b a r a b a  b b  a a b b a

Implementuj proponowany algorytm Maszyna Turinga dodaje jeden do liczby na taśmie. Słowo wejściowe składa się z cyfr całkowitych dziesiętny zapisane w kolejnych komórkach na taśmie. W początkowym momencie samochód znajduje się naprzeciwko skrajnej prawej cyfry numeru. a 0 0 1 2 3 4 ... 7 8 9 q 1 1H q 0 1H q 0 2H q 0 3H q 0 4H q 0 5H q 0 ... 8H q 0 9H q 0 0L q 1

Implementuj proponowany algorytm Taśma maszyny Turinga zawiera ciąg symboli „+”. Maszyna Turinga zastępuje co drugi symbol „+” „-”. Wymiana zaczyna się na prawym końcu sekwencji. Automat w stanie q 1 patrzy na jeden z symboli podanego ciągu. a 0 + - q 1 a 0 L q 2 + P q 1 q 2 a 0 H! + Л q 3 q 3 а 0 Н! - Л q 2 q 1 - maszyna szuka prawego końca numeru; q 2 - pomija znak "+", po osiągnięciu końca sekwencji - stop; q 3 - znak „+” zostaje zastąpiony przez „-”.

Przykład Mając maszynę Turinga z zewnętrznym alfabetem A = (a 0, 1, *), alfabetem stanów wewnętrznych Q = (q 0, q 1, q 2, q 3) i następującym schematem funkcjonalnym: Zastosuj Turinga maszyna do słowa  = 11 * 1 zaczynając od standardowej pozycji startowej

Rozwiązanie 1) Zamień zawartość obserwowanej komórki 1 na 0

Rozwiązanie 2) Maszyna wchodzi w nowy stan q 2

Rozwiązanie 3) Karetka przesuwa się w lewo

Rozwiązanie Kompletne szczegółowe rozwiązanie

Rozwiązanie Kompletne szczegółowe rozwiązanie

Rozwiązanie Rozwiązanie napisane z konfiguracjami (w linii)

 = 1 * 11 Odpowiedź:  = 111

Literatura Igoszyn V.I. Logika matematyczna i teoria algorytmów. - M .: Akademia, 2008 .-- 448 s. Lichtarnikow L.M., Sukaczewa T.G. Logika matematyczna. Kurs wykładowy. Praktyczna książka problemów i rozwiązań. - SPb .: Lan, 1999 .-- 288 s. Ilinich A.P. Teoria algorytmów. Instruktaż... - Jekaterynburg, 2006 .-- 149 pkt.

Ludzie mogą zachowywać się inaczej w tych samych sytuacjach iw tym zasadniczo różnią się od maszyn.

Alan Turing

Alan Mathison Turing Alan Mathison Turing (angielski Alan Mathison Turing; 23 czerwca 1912 – 7 czerwca 1954) – angielski matematyk, logik, kryptograf, który miał znaczący wpływ na rozwój informatyki. Komandor Orderu Imperium Brytyjskiego (1945), członek Royal Society of London (1951). Zaproponowana przez niego w 1936 roku abstrakcyjna „Maszyna Turinga”, którą można uznać za uniwersalny model komputerowy, umożliwiła sformalizowanie pojęcia algorytmu i jest nadal wykorzystywana w wielu badaniach teoretycznych i praktycznych. Prace naukowe A. Turing jest uznanym wkładem w podstawy informatyki (a w szczególności teorii sztucznej inteligencji).

Czas wojny Podczas II wojny światowej Alan Turing pracował w Rządowej Szkole Kodów i Szyfrów w Bletchley Park, gdzie koncentrowały się prace nad łamaniem szyfrów i kodów Osi. Kierował grupą Hut 8, która jest odpowiedzialna za kryptoanalizę wiadomości z niemieckiej marynarki wojennej. Turing opracował szereg technik hakerskich, w tym teoretyczne podstawy Bomby, maszyny używanej do włamywania się do niemieckiego urządzenia szyfrującego Enigma.

Maszyna Turinga W ciągu kilku tygodni po przybyciu do Blatchley Park Turing napisał specyfikacje maszyny elektromechanicznej, która mogłaby pomóc w złamaniu Enigmy skuteczniej niż polska bomba kryptologiczna. Maszyna Turinga, z ulepszeniami zaproponowanymi przez matematyka Gordona Welchmana, stała się podstawowym narzędziem do odszyfrowywania komunikatów Enigmy. Samochód został nazwany Bombe. Maszyna wyszukała możliwe ustawienia używane do szyfrowania wiadomości (kolejność wirników, pozycja wirnika, połączenia paneli krosowniczych) na podstawie znanego tekstu jawnego. Dla każdego możliwego ustawienia wirnika (który miał 1019 stanów lub 1022 w modyfikacji stosowanej na okrętach podwodnych) maszyna dokonała szeregu założeń logicznych na podstawie tekstu jawnego (jego treści i struktury). Następnie maszyna zidentyfikowała sprzeczność, odrzuciła zestaw parametrów i przeszła do następnego. W ten sposób większość możliwych zestawów została wyeliminowana i pozostało tylko kilka opcji do dokładnej analizy. Pierwszy pojazd wszedł do służby 18 marca 1940 roku. Numeracja klawiszy odbywała się dzięki obrotowi mechanicznych bębnów, czemu towarzyszył dźwięk podobny do tykania zegara.

Kolos W lipcu 1942 r. Turing brał udział w rozszyfrowaniu kodu Lorenza używanego przez Niemców do przesyłania wiadomości do naczelnego dowództwa. „Lorenz” był znacznie bardziej złożony niż „Enigma” i nie można go było rozszyfrować istniejącymi metodami. Turing zaproponował zastosowanie lamp próżniowych w konstrukcji dekodera i sprowadził zespół T. Flowersa, doświadczonego elektronika. W wyniku wspólnych wysiłków matematyków i inżynierów powstał „Colossus” – jeden z pierwszych komputerów na świecie. Do 1944 roku z pomocą Colossusa złamano kod Lorenza, który pozwolił aliantom na odczytanie całej korespondencji najwyższych niemieckich przywódców. Według niektórych szacunków przybliżyło to klęskę Niemiec o kilka lat.

Wczesne komputery i test Turinga Od 1945 do 1947 Turing mieszkał w Richmond i pracował nad ACE (Automatic Computing Engine) w National Physics Laboratory. 19 lutego 1946 przedstawił coś, co można by nazwać pierwszym szczegółowym opisem komputera z programem zapisanym w pamięci. Poprzedziła go niedokończona praca von Neumanna „First Draft EDVAC Report” (1945), ale była znacznie mniej szczegółowa i według kierownika wydziału matematyki National Physics Laboratory – Johna Wurmsleya: zawiera szereg pomysłów, które należą do dr. Turinga. Chociaż budowa ACE była możliwa, tajemnica otaczająca Blatchley Park doprowadziła do opóźnień w rozpoczęciu prac, co rozczarowało Turinga. Pod koniec 1947 roku wrócił do Cambridge na roczny urlop, podczas którego produktywnie pracował nad Inteligentną Maszyną, która nie została opublikowana za jego życia. Podczas gdy Alan Turing był w Cambridge, ACE Pilot został zbudowany pod jego nieobecność. Swój pierwszy program wykonał 10 maja 1950 roku. Pomimo pełna wersja ACE nigdy nie zostało zbudowane, niektóre komputery miały z nim wiele wspólnego np. DEUCE i Bendix G-15

W 1948 roku Alan Turing otrzymał tytuł Czytelnika na Wydziale Matematyki Uniwersytetu w Manchesterze. Tam w 1949 roku został dyrektorem Laboratorium Komputerowego, gdzie koncentrowało się programowanie Manchester Mark I. W tym samym czasie Turing kontynuował pracę nad bardziej abstrakcyjnymi problemami matematycznymi, a w swojej pracy „Computing Machinery and Intelligence” Mind ", październik 1950) zwrócił się do problemu sztucznej inteligencji i zaproponował eksperyment, który później stał się znany jako test Turinga. Jego pomysł polegał na tym, że komputer można uznać za „myślący”, jeśli osoba z nim współpracująca nie może odróżnić komputera od innej osoby w procesie komunikacji. W tej pracy Turing zasugerował, że zamiast próbować stworzyć program symulujący umysł dorosłego, znacznie łatwiej byłoby zacząć od umysłu dziecka, a następnie go uczyć. CAPTCHA oparta na odwróconym teście Turinga jest szeroko rozpowszechniona w Internecie. W 1948 r. Alan wraz ze swoim byłym kolegą Davidem Champernovnem (angielskim) zaczęli pisać program szachowy na komputer, który jeszcze nie istniał. W 1952 roku, nie mając odpowiedniego urządzenia do jego wykonania, Turing grał w grę, w której symulował działanie maszyny, wykonując jeden ruch co pół godziny. Mecz został nagrany i w rezultacie program przegrał z kolegą Turinga Alec Glini, ale wygrał mecz nad żoną Champernovny. Turing wynalazł również metodę rozszerzania LU w 1948 roku, która jest obecnie używana do rozwiązywania równań.

Slajd 2

Wstęp

Pojęcie algorytmu. Algorytm jest dokładną receptą, która określa proces obliczeniowy przechodzący od zmiennych danych początkowych do pożądanego wyniku (Markov A.A.) Właściwości algorytmu: 1) Dyskretność. 2) Pewność. 3) Skuteczność. 4) Charakter masowy.

Slajd 3

Model matematyczny maszyny Turinga

Maszyna Turinga (MT) to matematyczny model wyidealizowanej cyfrowej maszyny obliczeniowej. Urządzenie maszyny Turinga. Wstążka. Czytanie głowy. Urządzenie sterujące. Pamięć wewnętrzna.

Slajd 4

wstążka

Tylko jeden symbol (litera) z alfabetu zewnętrznego A = (˄, a1, a2,…, an-1), 2≥n może być wpisany do komórek w dyskretnym momencie. Pusta komórka jest oznaczona symbolem ˄, a sam symbol ˄ nazywany jest pustym, podczas gdy pozostałe znaki są określane jako niepuste.

Slajd 5

Czytanie głowy

Głowica może odczytać zawartość komórki i wpisać do niej nowy znak z alfabetu A. W jednym cyklu pracy może przesunąć tylko jedną komórkę w prawo (P), w lewo (L) lub pozostać na miejscu (H ).

Slajd 6

Pamięć wewnętrzna

Pamięć wewnętrzna maszyny to pewien skończony zbiór stanów wewnętrznych Q = (q0, q1,…, qm), m≥ 1. Zakładamy, że liczność | Q | ≥2. Szczególne znaczenie mają dwa stany maszyny: q1 to początkowy stan wewnętrzny (może być kilka początkowych stanów wewnętrznych), q0 to stan końcowy lub stan zatrzymania (stan końcowy jest zawsze jeden). W każdym momencie MT charakteryzuje się pozycją głowy i stanem wewnętrznym.

Slajd 7

Urządzenie sterujące

Wykonuje następujące czynności: Zmienia znak ai odczytany w czasie t na nowy znak aj (w szczególności pozostawia go bez zmian, czyli ai = aj); Przesuwa głowę w jednym z następujących kierunków: N, L, R; Zmienia stan wewnętrzny maszyny qi istniejący w czasie t na nowy qj, w którym maszyna będzie w czasie t+1. Takie działania urządzenia sterującego nazywamy poleceniem, które można zapisać w postaci: qiaiajDqj

Slajd 8

Obsługa maszyny Turinga

Działanie maszyny jest całkowicie zdeterminowane zadaniem w pierwszym (początkowym) momencie: Słowa na taśmie, czyli sekwencja znaków zapisanych w komórkach taśmy (słowo uzyskuje się czytając te znaki wzdłuż komórek taśmy od lewej do prawej); pozycje głowy; Stan wewnętrzny maszyny.

Slajd 9

Jeżeli w momencie początkowym na taśmie zapisane jest słowo a1, a2, ˄, a1, a1, to początkowa konfiguracja będzie wyglądać następująco: Działanie maszyny Turinga polega na sekwencyjnym aplikowaniu poleceń, ponadto jedno lub polecenie jest określone przez bieżącą konfigurację. Tak więc w powyższym przykładzie należy zastosować polecenie z lewą stroną q1a1. Wynikiem działania automatu jest słowo, które zostanie zapisane na taśmie w konfiguracji końcowej, czyli takiej, w której stan wewnętrzny automatu wynosi q0.

Slajd 10

Przykłady maszyn Turinga

Przykład 1. Skonstruuj maszynę Turinga T1, która ma zastosowanie do wszystkich słów z zewnętrznym alfabetem (a, b) i wykonuje następujące czynności: dowolne słowo x1, x2 ... xn, gdzie xi = a lub xi = b (i = 1, 2 ... n) zamienia się na słowo x2, ... xn, x1, czyli rozpoczynając pracę ze słowem x1, x2 ... xn na taśmie w konfiguracji początkowej, maszyna zatrzyma się, a w ostatecznej konfiguracji na jakimś odcinku taśmy słowo x2, ... xn, x1 i wszystkie inne komórki taśmy (jeśli są) będą puste.

Slajd 11

Rozwiązanie: Dla zewnętrznego alfabetu maszyny T1 przyjmujemy zbiór A = (˄, a, b), a dla wewnętrznego - Q = (q0, q1, q2, q3). Polecenia definiuje się następująco: q1a ˄Пq2, q1b ˄Пq3, qiy ˄PPi, gdzie yϵ (a, b), i = 2, 3; q2˄ aHq0, q3˄ bHq0 Rozważmy działanie maszyny T1 na słowie ba. W działaniu maszyny na słowie ba konfiguracja początkowa wygląda następująco:

Krótszy zapis tej sekwencji konfiguracji, czyli procesu działania maszyny, będzie następujący: Tak więc słowo bbabb jest przekształcane przez maszynę w słowo babbb.

Zobacz wszystkie slajdy