Który, zapożyczając pomysł od Emila Posta, wpadł na niego, podobno, w 1936 roku. Mimo dość skomplikowanej definicji formalnej pomysł jest w zasadzie prosty. Aby to zrozumieć, przespacerujmy się po stronach Wikipedii.
Przede wszystkim dochodzimy do strony, która w rzeczywistości nazywa się „maszyną Turinga”.
Maszyna Turinga
Maszyna Turinga (MT)- abstrakcja matematyczna reprezentująca ogólny typ komputera. Został zaproponowany przez Alana Turinga w roku, aby sformalizować koncepcję algorytmu.
Maszyna Turinga jest rozszerzeniem modelu automatu skończonego i zgodnie z tezą Churcha-Turinga jest zdolna do naśladowania (jeśli istnieje odpowiedni program) dowolnej maszyny, której działanie polega na przejściu z jednego stanu dyskretnego do drugiego.
Kompozycja maszyny Turinga obejmuje nieskończoną liczbę w obu kierunkach wstążka, podzielone na komórki i urządzenie sterujące ze skończoną liczbą stanów.
Urządzenie sterujące może poruszać się w lewo iw prawo wzdłuż taśmy, odczytywać i zapisywać do komórek znaki jakiegoś skończonego alfabetu. Specjalny pusty symbol, 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.
Urządzenie sterujące zawiera skok tabeli, który reprezentuje algorytm, wykonalny biorąc pod uwagę maszynę Turinga. Każda reguła z tabeli nakazuje maszynie, w zależności od aktualnego stanu i symbolu obserwowanego w bieżącej komórce, zapisanie nowego symbolu do tej komórki, 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 każda kombinacja stanu i symbolu wstążki w tabeli odpowiada co najwyżej jednej regule oraz niedeterministyczny Inaczej.
Tak więc maszyna Turinga jest matematyczną abstrakcją, spekulacyjną konstrukcją ludzkiego umysłu: nie istnieje w naturze. Czy jest tam? Od razu przychodzi na myśl, jak działa żywa komórka. Co najmniej dwa przykłady.
1. Do produkcji białek w komórce za pomocą złożonego enzymu - polimerazy RNA - informacje są odczytywane z DNA, rodzaj taśmy informacyjnej maszyny Turinga. Tutaj jednak komórki samej taśmy nie są nadpisywane, ale poza tym proces jest bardzo podobny: polimeraza RNA siedzi na DNA i porusza się wzdłuż niego w jednym kierunku, podczas gdy syntetyzuje nić RNA - kwas nukleinowy podobny do DNA. Gotowy RNA, odłączając się od enzymu, przenosi informacje do organelli komórkowych, w których wytwarzane są białka.
2. Proces poprawiania błędów w DNA jest jeszcze bardziej podobny do maszyny Turinga - jej naprawy. Tutaj polimeraza DNA wraz z innymi białkami porusza się wzdłuż taśmy DNA i odczytuje jej obie połowy (genomowy DNA, jak wiadomo, składa się z dwóch splecionych nici niosących te same informacje). Jeśli informacje w połówkach nie pasują do siebie, polimeraza DNA bierze za model jedną z nich i „rządzi” drugą.
Taka analogia nie jest nowa, a na Wikipedii jest również opisana w artykule „Komputer molekularny”:
komputer molekularny
Obliczenia biomolekularne lub komputery molekularne a nawet obliczanie DNA - lub RNA - wszystkie te terminy pojawiły się na styku tak różnych nauk, jak genetyka molekularna i technologia komputerowa.
Obliczenia biomolekularne to zbiorowa nazwa dla różnych technik związanych w taki czy inny sposób z DNA lub RNA. W obliczeniach DNA dane nie są prezentowane w postaci zer i jedynek, ale w postaci struktury molekularnej zbudowanej na bazie helisy DNA. Rolę oprogramowania do odczytu, kopiowania i zarządzania danymi spełniają specjalne enzymy.
Podstawą całego biologicznego systemu przechowywania informacji, a więc komputerów DNA, jest zdolność do wzajemnego przyciągania się atomów wodoru wchodzących w skład związków azotowych (adeniny, tyminy, cytozyny i guaniny) w określonych warunkach, tworzących niewalentne pary związane. Z drugiej strony, substancje te mogą wiązać się wartościowo z kombinacją cząsteczki cukru (deoksyrybozy) i fosforanu, tworząc tzw. nukleotydy. Z kolei nukleotydy z łatwością tworzą polimery o długości dziesiątek milionów zasad. W tych supercząsteczkach fosforan i dezoksyryboza pełnią rolę struktury podtrzymującej (zamieniają się w łańcuchu), podczas gdy związki azotowe kodują informację.
Cząsteczka okazuje się być skierowana: zaczyna się od grupy fosforanowej, a kończy na dezoksyrybozie. Długie nici DNA nazywane są nićmi, krótkie nazywane są oligonukleotydami. Każda cząsteczka DNA odpowiada innemu DNA - tak zwanemu dopełniaczowi Watsona-Cricka. Ma przeciwny kierunek niż pierwotna cząsteczka. W wyniku przyciągania adeniny do tyminy i cytozyny do guaniny powstaje słynna podwójna helisa, która umożliwia duplikację DNA podczas rozmnażania komórek. Zadanie podwojenia rozwiązuje się za pomocą specjalnego enzymu białkowego - polimerazy. Synteza zaczyna się tylko wtedy, gdy fragment jego dopełniacza jest dołączony do DNA.Właściwość ta jest aktywnie wykorzystywana w biologii molekularnej i obliczeniach molekularnych. W swej istocie DNA + polimeraza to implementacja maszyny Turinga, składająca się z dwóch taśm i programowalnego panelu sterowania. Pilot odczytuje dane z jednej taśmy, przetwarza je według jakiegoś algorytmu i zapisuje na innej taśmie. Polimeraza odczytuje również sekwencyjnie dane wyjściowe z jednej taśmy (DNA) i na ich podstawie tworzy niejako taśmę z wynikami obliczeń (dodanie Watsona-Cricka).
Nieco fantastyczne perspektywy tylko podsycają naszą ciekawość. Tymczasem nie ustaliliśmy jeszcze wszystkiego na temat maszyny Turinga. Jak pamiętacie, w artykule na Wikipedii nazwano to rozszerzeniem maszyny stanowej. Czym jest maszyna skończona? Na szczęście jest do tego link. Przechodząc przez nią dowiadujemy się, że:
maszyna stanowa
Automaty abstrakcyjne tworzą podstawową klasę modeli dyskretnych, zarówno jako model sam w sobie, jak i jako główny składnik maszyn Turinga, automatów ze spadkiem, automatów skończonych i innych konwerterów informacji.
Z każdą definicją coraz bardziej wkraczamy w sferę czystej matematyki. Język staje się zaostrzony, pojawiają się definicje formalne, składające się z symboli matematycznych. Jeśli pójdziemy dalej, dojdziemy do teorii algorytmów i teorii obliczalności. Możesz długo podróżować po stronach Wikipedii, ale lepiej zaopatrzyć się w wodę i żywność na wypadek, gdybyś zawędrował na pustynię aksjomatów i definicji, lub przynajmniej wiarygodne linki do podręczników z matematyki, na przykład http: //www.mccme.ru/free-books/ lub artykuły z magazynu „Potencjał”;)
Mam nadzieję, że po tym wyjaśnieniu stało się dla ciebie trochę jaśniejsze, czym dokładnie jest maszyna Turinga?
Wróćmy do historii tego terminu.
Tak więc, jak już wspomnieliśmy, Alan Turing opowiedział światu o swojej maszynie w 1937 roku w tak zwanej tezie Church-Turing. O Alanie Turingu - pierwszym hakerze i pionierze informatyki, jak napisano na tablicy pamiątkowej hotelu, w którym się urodził, opowie nam artykuł "Alan Turing". Nie podamy tutaj pełnego tekstu artykułu, ale sam w sobie nie jest on bardzo szczegółowy.
Alan Turing
Turing, Alan Mathison(23 czerwca 1912 - 7 czerwca 1954) - angielski matematyk, logik, kryptograf, wynalazca maszyny Turinga.
Sam artykuł jest bardziej o pracy Turinga: oprócz tekstu o maszynie Turinga, który podamy później, mówi się, że pracował nad „problemem z wiszącym” (zabawne, prawda? Nie było jeszcze komputerów , a także Windows, ale wystąpił już problem z zawieszaniem się.); heroiczna opowieść o tym, jak Turing złamał kod Enigmy podczas II wojny światowej i tym samym ocalił Wielką Brytanię; fakt, że jest twórcą teorii sztucznej inteligencji, a także wzmianka o słynnym teście Turinga. Teraz ten test nie jest już często używany jako początek opowieści science fiction, ale problem człowieka w maszynie na zawsze pozostanie klasykiem, jak powieści Izaaka Asimowa i Stanisława Lema.
Pomimo tego, że jest staromodny, test Turinga w nieoczekiwany sposób pojawił się w dzisiejszym świecie komunikacji internetowej. Na przykład możesz spotkać się z tekstem dialogu dwóch użytkowników ICQ, z których jeden jest „botem”, a zadaniem jest ustalenie, który z nich. Albo nieznany użytkownik, na przykład robot ICQ, może zapukać do twoich drzwi. Rozpoznajesz go? Studiując teorię, możesz być w stanie zastosować test Turinga na czas i nie dać się oszukać. Możesz rozpocząć badanie od odpowiedniego artykułu w Wikipedii, a następnie skorzystać z linków podanych na końcu artykułu:
Test Turinga
Test Turinga- test zaproponowany przez Alana Turinga w 1950 roku w artykule „Maszyny komputerowe i inteligencja”, aby sprawdzić, czy komputer jest inteligentny w ludzkim znaczeniu tego słowa.
Sędzia (człowiek) koresponduje w języku naturalnym z dwoma rozmówcami, z których jeden jest człowiekiem, a drugi komputerem. Jeśli sędzia nie może wiarygodnie określić, kto jest kim, komputer zdał test. Zakłada się, że każdy z rozmówców dąży do uznania za osobę. Aby test był prosty i uniwersalny, korespondencja sprowadza się do wiadomości tekstowych.
Korespondencja musi odbywać się w kontrolowanych odstępach czasu, aby sędzia nie mógł wyciągnąć wniosków z szybkości odpowiedzi. (W czasach Turinga komputery reagowały wolniej niż ludzie. Teraz ta zasada jest konieczna, ponieważ reagują znacznie szybciej niż ludzie.)
Test został zainspirowany grą towarzyską, w której goście próbowali odgadnąć płeć osoby w innym pokoju, pisząc pytania i czytając odpowiedzi. W pierwotnym sformułowaniu Turinga osoba musiała udawać osobę płci przeciwnej, a test trwał 5 minut. Teraz te zasady nie są uważane za konieczne i nie są uwzględnione w specyfikacji testu.
Turing zaproponował test, aby zastąpić bezsensowne, jego zdaniem, pytanie „czy maszyna może myśleć?” do bardziej konkretnego.
Turing przewidział, że komputery w końcu zdadzą jego test. Uważał, że do roku 2000 komputer z pamięcią 1 miliarda bitów (około 119 MB) w 5-minutowym teście może oszukać sędziów w 30% przypadków. Ta przepowiednia się nie sprawdziła. (Wprawdzie na pierwszym konkursie Loebnera program komputerowy „PC Therapist” na IBM PC 386 zdołał oszukać 5 na 10 sędziów, ale nie liczył wyniku, a w 1994 r. zawody zostały utrudnione.) Turing Przewidywali również, że połączenie „myślącej maszyny” nie będzie uważane za oksymoron, a trening komputerowy będzie odgrywał ważną rolę w budowaniu potężnych komputerów (z czym zgadza się większość współczesnych badaczy).
Jak dotąd żaden program nie zbliżył się nawet do zdania testu. Programy takie jak ELIZA czasami sprawiały, że ludzie wierzyli, że rozmawiają z osobą, jak w nieformalnym eksperymencie zwanym AOLiza. Ale takie „sukcesy” nie zdają testu Turinga. Po pierwsze, osoba w takich rozmowach nie miała powodu sądzić, że rozmawia z programem, podczas gdy w prawdziwym teście Turinga osoba aktywnie próbuje ustalić, z kim rozmawia. Po drugie, udokumentowane przypadki są zwykle w pokojach rozmów, takich jak IRC, gdzie wiele rozmów jest pobieżnych i bezsensownych. Po trzecie, wielu użytkowników IRC używa angielskiego jako drugiego lub trzeciego języka, a bezsensowna reakcja programu jest prawdopodobnie przypisana barierze językowej. Po czwarte, wielu użytkowników nie wie nic o Elise i podobnych programach i nie może rozpoznać całkowicie nieludzkich błędów, które te programy popełniają.
Co roku odbywa się konkurencja między programami mówiącymi, a najbardziej ludzki, zdaniem jurorów, otrzymuje nagrodę Loebnera. Istnieje dodatkowa nagroda za program, który zdaniem sędziów zda test Turinga. Ta nagroda nie została jeszcze przyznana.
Najlepszy wynik w teście Turinga wykazał program A.L.I.C.E. wygrywając test 3 razy (w 2000, 2001 i 2004).
Spinki do mankietów
- Turing A. M. Maszyny obliczeniowe a umysł. // W: Hofstader D., Dennett D. Oko umysłu. - Samara: Bahrakh-M, 2003. - S. 47-59.
- Książka w języku angielskim: Roger Penrose „Nowy umysł cesarza”.
- Artykuł Alana Turinga:
- Alan Turing, Maszyny komputerowe i inteligencja, Umysł, tom. LIX, nie. 236, październik 1950, s. 433-460.
- Online:
- Artykuł G. Oppy i D. Dowe na temat testu Turinga ze Stanford Encyclopedia of Philosophy (w języku angielskim)
- „Test Turinga: 50 lat później” przegląd 50 lat pracy nad testem Turinga, z punktu widzenia roku 2000 (w języku angielskim).
Wracamy ponownie do maszyny Turinga. We fragmencie artykułu o Alanie Turingu stwierdza się, że po raz pierwszy zaproponowano koncepcję maszyny Turinga w ramach tzw. Teza Kościoła Turinga:
Fragment artykułu z Wikipedii „Alan Turing”
Każda intuicyjnie obliczalna funkcja jest częściowo obliczalna lub, równoważnie, może zostać obliczona przez jakąś maszynę Turinga.
Alan Turing zasugerował (znany jako teza Churcha-Turinga), że każdy algorytm w intuicyjnym znaczeniu tego słowa może być reprezentowany przez równoważną maszynę Turinga. Udoskonalenie koncepcji obliczalności opartej na koncepcji maszyny Turinga (i innych koncepcji jej równoważnych) otworzyło możliwości rygorystycznego dowodu nierozwiązywalności algorytmicznej różnych problemów masowych (tj. problemów ze znalezieniem zunifikowanej metody rozwiązania pewnego klasę problemów, których warunki mogą się różnić w określonych granicach). Najprostszym przykładem algorytmicznie nierozstrzygalnego problemu masy jest tzw. problem stosowalności algorytmu (zwany również problemem zatrzymania). Polega ona na tym, że: należy znaleźć ogólną metodę, która pozwoliłaby dowolnej maszynie Turinga (podanej przez jej program) i dowolnym początkowym stanie taśmy tej maszyny określić, czy działanie tej maszyny kończy się skończoną liczbą kroków, czy będzie trwać w nieskończoność.
W artykule zatytułowanym „Teza Turinga Kościoła” piszą o nim tak:
Teza Kościoła Turinga
Teza Kościoła Turinga- fundamentalne stwierdzenie dla wielu dziedzin nauki, takich jak teoria obliczalności, informatyka, cybernetyka teoretyczna itp. Oświadczenie to wygłosili Alonzo Church i Alan Turing w połowie lat 30. XX wieku.
W swojej najbardziej ogólnej formie stwierdza, że każda intuicyjnie obliczalna funkcja jest częściowo obliczalna lub równoważnie, może być obliczona przez jakąś maszynę Turinga.
Tezy Churcha-Turinga nie można rygorystycznie udowodnić ani obalić, ponieważ ustanawia ona „równość” między ściśle sformalizowanym pojęciem częściowo obliczalnej funkcji a nieformalnym pojęciem „funkcji obliczalnej intuicyjnie”.
Teza fizyczna Kościoła Turinga brzmi: Każda funkcja, która może być obliczona przez urządzenie fizyczne, może być obliczona przez maszynę Turinga.
Z tego skrzyżowania można przejść na przykład w kierunku teorii obliczalności. Możesz też spróbować dowiedzieć się, kim jest ten tajemniczy Kościół, z którym Alan Turing przedstawił swoją tezę.
Uniwersalna maszyna Turinga
Uniwersalna maszyna Turinga nazywana maszyną Turinga, która może zastąpić dowolną maszynę Turinga. Po otrzymaniu programu i danych wejściowych jako danych wejściowych, oblicza odpowiedź, którą maszyna Turinga, której program został podany jako dane wejściowe, obliczyłaby na podstawie danych wejściowych.
Formalna definicja
Program dowolnej deterministycznej maszyny Turinga można napisać przy użyciu jakiegoś skończonego alfabetu składającego się z symboli stanów, nawiasów, strzałek i tak dalej; oznaczmy ten alfabet maszynowy jako Σ 1 (\ Displaystyle \ Sigma _ (1)). Następnie uniwersalna maszyna Turinga U dla klasy maszyn z alfabetem Σ 2 (\ Displaystyle \ Sigma _ (2)) oraz k taśmy wejściowe nazywa się maszyną Turinga z k+1 taśma wejściowa i alfabet Σ 1 ∪ Σ 2 (\ Displaystyle \ Sigma _ (1) \ filiżanka \ Sigma _ (2)) tak, że jeśli złożysz wniosek o pierwszy k wartość wejściowa taśm i włączony k+1 jest poprawnym kodem jakiejś maszyny Turinga, to U da taką samą odpowiedź, jaką dałby na tych wejściach M 1 (\displaystyle M_(1)), lub będzie działać w nieskończoność, jeśli M 1 (\displaystyle M_(1)) nie poprzestawaj na tych danych.
Uniwersalne twierdzenie o maszynie Turinga stwierdza, że taka maszyna istnieje i modeluje inne maszyny z co najwyżej kwadratowym opóźnieniem (to znaczy, jeśli oryginalna maszyna wyprodukowana T kroki, wtedy uniwersalny wyprodukuje co najwyżej ct2). Dowód tego twierdzenia jest konstruktywny (taka maszyna jest łatwa do zbudowania, wystarczy ją dokładnie opisać). Twierdzenie zostało zaproponowane i udowodnione przez Turinga w latach 1936-37.
Implementacja oprogramowania w języku programowania Delphi jest dość prosta. Jedną z tych implementacji można znaleźć pod adresem http://kleron.ucoz.ru/load/24-1-0-52 . Możliwe jest wczytanie i zapisanie do pliku Excel.
Niedeterministyczna maszyna Turinga
Probabilistyczna maszyna Turinga
Uogólnienie deterministycznej maszyny Turinga, w której z dowolnego stanu i wartości na taśmie maszyna może dokonać jednego z kilku (można rozważyć, bez utraty ogólności - dwóch) możliwych przejść i dokonać wyboru w sposób probabilistyczny (rzucanie monetą).
Probabilistyczna maszyna Turinga jest podobna do niedeterministycznej maszyny Turinga, tyle że zamiast niedeterministycznego przejścia maszyna wybiera z pewnym prawdopodobieństwem jedną z opcji.
Istnieje również alternatywna definicja:
Probabilistyczna maszyna Turinga to deterministyczna maszyna Turinga, która dodatkowo posiada sprzętowe źródło losowych bitów, których dowolna liczba, na przykład, może „zamawiać” i „ładować” na osobną taśmę, a następnie wykorzystywać w obliczeniach w zwykły sposób dla MT.
Klasa algorytmów, które kończą się w czasie wielomianowym na probabilistycznej maszynie Turinga i zwracają odpowiedź z błędem mniejszym niż 1/3, nazywana jest klasą BPP.
W 1936 roku Alan Turing zaproponował wyjaśnienie pojęcia algorytmu abstrakcyjny uniwersalny wykonawca. Jego abstrakcyjność polega na tym, że jest logiczną konstrukcją obliczeniową, a nie prawdziwym komputerem. Termin „wykonawca uniwersalny” oznacza, że wykonawca ten może naśladować każdego innego wykonawcę. Na przykład operacje, które wykonują prawdziwe komputery, mogą być symulowane na uniwersalnym executorze. W konsekwencji wynaleziona przez Turinga konstrukcja obliczeniowa została nazwana Maszyna Turinga.
Ponadto zakłada się, że uniwersalny wykonawca powinien być w stanie udowodnić istnienie lub brak algorytmu dla określonego zadania.
Co to jest maszyna Turinga?
Maszyna Turinga składa się z taśmy, która jest nieskończona w obu kierunkach, podzielona na komórki oraz automatu (głowicy), którym steruje program.
Programy dla maszyn Turinga napisane są w formie tabeli, w której pierwsza kolumna i wiersz zawierają litery alfabetu zewnętrznego oraz możliwe stany wewnętrzne automatu (alfabet wewnętrzny). Zawartość tabeli to instrukcje dla maszyny Turinga. Litera, którą nagłówek odczytuje w komórce (w której aktualnie się znajduje) oraz stan wewnętrzny nagłówka określają, którą instrukcję wykonać. Polecenie jest określane przez przecięcie znaków alfabetu zewnętrznego i wewnętrznego w tabeli.
Aby określić konkretną maszynę Turinga, należy opisać dla niej następujące elementy:
- alfabet zewnętrzny. Zbiór skończony (na przykład A), którego elementy nazywamy literami (symbołami). Jedna z liter tego alfabetu (na przykład 0) musi być pustym znakiem.
- alfabet wewnętrzny. Skończony zbiór stanów głowicy (automatu). Jeden ze stanów (na przykład q 1) musi być początkowy (uruchamianie programu). Jeszcze jeden ze stanów (q 0) musi być końcowy (zakończenie programu) - stan zatrzymania.
- Skocz do stołu. Opis zachowania automatu (głowicy) w zależności od stanu i odczytywanego znaku.
Automat maszyny Turinga w trakcie swojej pracy może wykonywać następujące czynności:
- Wpisz do komórki znak alfabetu zewnętrznego (w tym pustą), zastępując w niej znak (w tym pustą).
- Przesuń jedną komórkę w lewo lub w prawo.
- Zmień swój stan wewnętrzny.
Jedno polecenie dla maszyny Turinga to po prostu specyficzna kombinacja tych trzech elementów: instrukcji, jaką postać wpisać do komórki (nad którą stoi maszyna), gdzie się poruszać i do jakiego stanu się udać. Chociaż polecenie może nie zawierać wszystkich komponentów (na przykład nie zmieniaj symbolu, nie przesuwaj lub nie zmieniaj stanu wewnętrznego).
Przykład maszyny Turinga
Załóżmy, że na taśmie znajduje się słowo składające się ze znaków #, $, 1 i 0. Chcesz zastąpić wszystkie znaki # i $ zerami. W momencie startu głowa znajduje się nad pierwszą literą słowa po lewej stronie. Program kończy się, gdy nagłówek znajdzie się nad pustym znakiem po skrajnej prawej literze słowa.
Notatka: długość słowa i kolejność znaków nie mają znaczenia. Rysunek przedstawia przykładową kolejność wykonywania poleceń dla konkretnego przypadku. Jeśli na taśmie jest inne słowo, kolejność poleceń będzie inna. Mimo to ten program dla maszyny Turinga (na rysunku - tabela po lewej) ma zastosowanie do dowolnych słów opisanego alfabetu zewnętrznego (zaobserwowana jest właściwość stosowalności algorytmu do wszystkich zadań tego samego typu - znak masy ).
Możesz skomplikować program. Załóżmy, że głowa niekoniecznie znajduje się nad pierwszym, ale nad dowolnym znakiem tego słowa. Wtedy program dla danej maszyny Turinga mógłby wyglądać tak (lub mógłby być inny):
Tutaj głowa jest przesunięta w lewo, aż znajdzie się nad pustym znakiem. Następnie maszyna wchodzi w stan q 2 (którego polecenia są takie same jak polecenia q 1 poprzedniego programu).
Postanowiłem wyjaśnić ludzkości zasadę obliczeń algorytmicznych. Faktem jest, że pan Turing był prorokiem ery komputerów, więc po prostu nie mógł powstrzymać się od opowiadania ludziom, czym jest algorytm. Wymyślił więc abstrakcyjną maszynę, która została nazwana jego imieniem. Mam na myśli nazwisko. Ale zróbmy to dobrze...
Esencja w prostych słowach
Należy natychmiast zidentyfikować ważny punkt: maszyna Turinga jest urządzeniem wyłącznie spekulacyjnym. Nic podobnego nie istnieje w naturze. Modele komputerowe istnieją. Nawet aktywne. Ale to nic innego jak modele.
Dlaczego? Ponieważ przedmiotem dyskusji jest niekończąca się taśma, której pełnoprawne fizyczne istnienie na tym etapie rozwoju nauki i techniki jest możliwe tylko teoretycznie.
Taśma składa się z komórek, jak łańcuch ogniw. Komórki zawierają dane, takie jak znaki alfabetyczne. Cóż, albo zera i jedynek. Ogólnie rzecz biorąc, coś odpowiedniego do automatycznego przetwarzania. Odbywa się to za pomocą ruchomej części maszyny.
Jak to działa
Częścią ruchomą jest czytelnik i pisarz. Coś, co potrafi odczytać zawartość komórek, zapisać w nich coś własnego i, co najważniejsze, działać zgodnie z wynikającymi z tego wynikami.
Co więcej, automat może poruszać tylko jedną komórkę na raz. Prawo, lewo, tam gdzie jest to konieczne do wykonania obliczeń. Dodałem tu coś - trzeba się ruszać, żeby coś zabrać. A potem ponownie spasuj. I tak długo, jak chcesz, aż zadanie zostanie wykonane. W końcu taśma jest nieskończona, jest wystarczająco dużo opcji dla każdej operacji.
W rzeczywistości Alan Turing starał się tylko podkreślić, że każde obliczenie, bez względu na jego złożoność, można wykonać etapami, krok po kroku, rozbijając zadanie na elementarne elementy. To jest istota algorytmu.
Różne warianty
Początkujący cybernetycy spojrzeli na maszynę Turinga i zrozumieli, że nie ma na co narzekać. Rzeczywiście, programy komputerowe powinny być budowane na podstawie algorytmów - wykonywania instrukcji krok po kroku.
Jednocześnie chwała Alana Turinga nie dała wielu odpoczynku, a wyznawcy zaczęli, jak mówią, wyłapywać jej refleksje. Zaczęli wymyślać wielowymiarowe maszyny Turinga, z wieloma taśmami, „pół-nieskończone” itp.
Postaramy się choć trochę rozjaśnić ten chaos i rozważyć realne opcje dla omawianego urządzenia.
- niedeterministyczny- jest to maszyna Turinga, która działa na taśmę z opisanymi powyżej ogniwami zgodnie z sytuacją, która pojawia się na danym etapie obliczeń. Innymi słowy, gdziekolwiek chce, przeniesie się tam.
- deterministyczny jeden z konkretnymi instrukcjami. Na przykład, jeśli komórka, w której znajduje się uruchamiający się automat, zawiera literę A, to musisz przejść do następnej, z literą B, czy tego chcesz, czy nie.
- Kompletny- potrafi obliczyć wszystko, co można obliczyć krok po kroku. Może nawet symulować maszynę w maszynie, emulator opisujący działanie innego podobnego urządzenia za pomocą algorytmów.
- uniwersalny- zdolny do wszystkiego, co potrafi każda maszyna Turinga. Ogólnie żaden, nawet jeszcze nie wynaleziony. Oczywiście jest kompletna.
Praktyczne korzyści
Oczywiście algorytm jest bardziej złożoną koncepcją niż tylko przenoszenie wykonania przez kroki w jednowymiarowej przestrzeni. W końcu możliwe są rozgałęzienia, pętle, powrót, używanie podprogramów.
Ponadto w praktyce niemożliwe jest zasymulowanie nieskończonej liczby komórek zawierających dane, choćby ze względu na ograniczone możliwości sprzętu komputerowego.
Istnieją jednak programy symulacyjne maszyny Turinga przeznaczone do nauczania studentów. Początkujących programistów zachęca się do opracowywania różnych algorytmów, na przykład wyszukiwania, zmiany, dodawania, przestawiania liter w komórkach.
Dlatego zalety maszyny Turinga są dokładnie tym, co zamierzał jej twórca, prorok ery komputerów: jasnym pokazem istoty obliczeń algorytmicznych.
Poprzednie publikacje:
Ostatnia edycja: 2013-04-01 10:58:05
Tagi materiałowe: ,
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 ) - zbiór stanów;
- 3) zestaw znaków kontrolnych (P, L, S)
- 4) niekończącą się taśmę w obu kierunkach, 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 zdolne do przebywania w jednym z wielu stanów;
Symbolem pustej komórki jest litera alfabetu zewnętrznego, czyli 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 zatrzymuje się.
Urządzenie sterujące może poruszać się w lewo iw prawo po taśmie, odczytywać i wpisywać do komórek taśmy litery alfabetu A. Urządzenie sterujące działa według poleceń, które mają następującą postać
q i a j > a p X q k
Wpis oznacza, że: jeżeli urządzenie sterujące jest w stanie qi, aw przeglądanej komórce jest zapisana litera aj, to (1) do komórki zamiast aj zapisywana jest 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 kontynuować wyświetlanie tej samej komórki taśmy, jeśli X=C, (3) urządzenie sterujące wchodzi w stan q k.
Ponieważ działanie maszyny, według stanu, jest całkowicie określone przez jej stan q w danym momencie i zawartość a oglądanej w tym momencie komórki, istnieje dokładnie jedna reguła dla każdej możliwej konfiguracji q i a j. Nie ma reguł tylko dla stanu końcowego, w którym maszyna się zatrzymuje. Dlatego program maszyny Turinga z alfabetem zewnętrznym A=(a0, a1, …, an) i alfabetem wewnętrznym Q=(q1, q2,…, qm) zawiera nie więcej niż 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. Pod k-tą konfiguracją mamy na myśli obraz taśmy maszyny z informacją, jaka się na niej rozwinęła przed początkiem k-tego kroku (lub słowem w alfabecie A napisanym na taśmie na początku k-ty krok), wskazując, która komórka jest oglądana na tym kroku A w jakim stanie jest samochód? Tylko skończone 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 ostateczna, jeśli stan maszyny jest ostateczny.
Jeżeli jako początkową wybierzemy dowolną nieostateczną konfigurację maszyny Turinga, to zadaniem maszyny jest sekwencyjne (krok po kroku) przekształcenie 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 (а 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 skanuje skrajnie lewą lub prawą komórkę z tych, w których jest napisane słowo b. Pozycja standardowa nazywana jest 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 doprowadza maszynę Turinga do stanu końcowego, mówi się, że dotyczy ono b, w przeciwnym razie nie dotyczy b (maszyna działa w nieskończoność)
Rozważ przykład:
Biorąc pod uwagę maszynę Turinga z zewnętrznym alfabetem A \u003d (0, 1) (tutaj 0 jest symbolem pustej komórki), alfabetem stanów wewnętrznych Q \u003d (q 0, q 1, q 2 ) i z następującymi schemat funkcjonalny (program):
q 1 0 > 1 l q 2 ;
q 1 1 > 0 С q 2 ;
q 2 0 > 0 П q 0 ;
q 2 1 > 1 C q 1;
Ten program można napisać za pomocą tabeli
W pierwszym kroku polecenie działa: q 1 0 > 1 Л q 2 (urządzenie sterujące znajduje się w stanie q1, a w monitorowanej komórce jest zapisana litera 0, zamiast 0 w komórce jest zapisana 1, głowica jest przesunięty w lewo, sterownik 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 jest w stanie zatrzymania q 0 .
W ten sposób oryginalne słowo 110 jest przetwarzane przez maszynę na słowo 101.
Wynikową sekwencję konfiguracji można zapisać w krótszy sposób (zawartość monitorowanej 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 pewna reguła (algorytm) przeliczania słów alfabetu A Q, czyli 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.
transkrypcja
1 Moskiewski Uniwersytet Państwowy Łomonosowa Śr. Łomonosowa Wydział Matematyki Obliczeniowej i Cybernetyki V.N. Pilszczikow, W.G. Abramow, AA Vylitok, I.V. Maszyna Hot Turinga i algorytmy Markowa. Rozwiązywanie problemów (podręcznik edukacyjny) Moskwa, 2006
2 UDC BBK P32 Pilshchikov V.N., Abramov V.G., Vylitok A.A., Hot I.V. Maszyna Turinga i algorytmy Markowa. Rozwiązywanie problemów. (Podręcznik edukacyjny) - M .: Moskiewski Uniwersytet Państwowy, s. Dział Wydawniczy WUM MSU (licencja LR od) Podręcznik poświęcony jest rozwiązywaniu problemów na temat „Wstęp do teorii algorytmów”, studiował na I roku Wydziału CMC MSU w ramach dyscypliny „Algorytmy i języki algorytmiczne”. Są to zadania kompilacji algorytmów w postaci maszyny Turinga i zwykłych algorytmów Markowa, a także zadania o charakterze teoretycznym. Podręcznik dostarcza niezbędnych informacji na temat teorii algorytmów, szczegółowo wyjaśnia typowe techniki rozwiązywania problemów i oferuje duży zestaw problemów do samodzielnego rozwiązania. Podręcznik przeznaczony jest dla studentów I roku wydziału CMC Moskiewskiego Uniwersytetu Państwowego oraz nauczycieli prowadzących seminaria z programowania. Recenzenci: docent Baula V.G. Docent Korukhova L.S. Opublikowany decyzją Rady Redakcyjnej i Wydawniczej Wydziału Matematyki Obliczeniowej i Cybernetyki Moskiewskiego Uniwersytetu Państwowego. Śr. Łomonosow. ISBN??? Wydział Wydawniczy Wydziału Matematyki Obliczeniowej i Cybernetyki Moskiewskiego Uniwersytetu im. Łomonosowa Śr. Łomonosow,
3 1. Maszyna Turinga Ta sekcja dotyczy problemów kompilacji algorytmów dla maszyny Turinga. Podano krótki opis tej maszyny, wyjaśniono główne metody kompilacji takich algorytmów na przykładach i zaproponowano problemy do samodzielnego rozwiązania. 1.1 Krótki opis maszyny Turinga Budowa maszyny Turinga Maszyna Turinga (MT) składa się z dwóch części taśmy i automatu (patrz po lewej): taśma: abb Λ Λ abb Λ Λ automat: qq Taśma służy do przechowywania Informacja. Jest nieskończony w obu kierunkach i jest podzielony na komórki, które nie są w żaden sposób ponumerowane ani nazwane. Każda komórka może zawierać jeden znak lub nic. Zawartość komórki może się w nią zmienić, możesz wpisać inny znak lub wymazać znajdujący się tam znak. Nazwijmy pustą zawartość komórki symbolem „pusta” i oznaczmy znak Λ („lambda”). Dlatego obraz taśmy pokazany na rysunku po prawej jest taki sam, jak na rysunku po lewej stronie. Konwencja ta jest wygodna, ponieważ operację usunięcia znaku w określonej komórce można uznać za wpisanie znaku Λ do tej komórki, więc zamiast długiej frazy „wpisz znak do komórki lub usuń znajdujący się tam znak” może po prostu powiedzieć „wpisz znak do komórki”. Maszyna jest aktywną częścią MT. W każdej chwili jest umieszczany pod jedną z komórek taśmy i widzi jej zawartość; to jest widoczna komórka, a symbol w niej jest widocznym symbolem; zawartość sąsiednich i innych komórek nie jest widoczna dla maszyny. Dodatkowo w każdej chwili automat znajduje się w jednym ze stanów, który będzie oznaczony literą q z liczbami: q1, q2 itd. Będąc w pewnym stanie automat wykonuje określoną operację (np. przesuwa się w prawo wzdłuż taśmy, zastępując wszystkie znaki b na a), będąc w innym stanie, inną operację. Para widocznego symbolu (S) i aktualny stan automatu (q) będzie nazywana konfiguracją i oznaczona
4 Cykl maszyny Turinga MT pracuje w cyklach, które są wykonywane jeden po drugim. W każdym cyklu automat MT wykonuje następujące trzy czynności, koniecznie we wskazanej kolejności: 1) zapisuje jakiś symbol S w widocznej komórce (w szczególności można zapisać ten sam symbol tak, jak w nim był, to zawartość ta komórka się nie zmienia); 2) przesuwa się o jedną komórkę w lewo (zapis L, od lewej) lub jedną komórkę w prawo (zapis R, od prawej) lub pozostaje nieruchomy (zapis N). 3) przechodzi w pewien stan q (w szczególności może pozostać w tym samym stanie). Formalnie działania jednego taktu zostaną zapisane jako trójka: S, , q gdzie konstrukcja z nawiasami kwadratowymi oznacza możliwość wpisania w tym miejscu dowolnej z liter L, R lub N. przesuń jedną komórkę w lewo i przejście do stwierdzenia q8. Program maszyny Turinga Sam w sobie MT nic nie robi. Aby to zadziałało, musisz napisać dla niego program. Program ten jest zapisany w postaci poniższej tabeli: q 1 qjqm S 1 S 2 S i S n Λ S, , q Po lewej stronie wymienione są wszystkie stany, w których może znajdować się automat, na górze wszystkie symbole (w tym Λ), które automat może zobaczyć na taśmie. (Jakie symbole i stany wskazać w tabeli określa autor programu.) Na przecięciach (w komórkach tabeli) wskazano te cykle, które automat musi wykonać, gdy jest w odpowiednim stanie i widzi odpowiedni symbol na taśmie. Ogólnie rzecz biorąc, tabela określa działania MT dla wszystkich możliwych konfiguracji, a tym samym całkowicie ustawia zachowanie MT. Opisanie algorytmu w postaci MT oznacza przedstawienie takiej tabeli. (Uwaga. Często MT jest definiowany jako składający się z taśmy, automatu i programu, więc różne programy produkują różne MT. Założymy, w duchu nowoczesnych komputerów, że istnieje tylko jedna MT, ale może ona wykonywać różne programów.) 4
5 Zasady wykonywania programu Przed uruchomieniem programu należy wykonać następujące czynności wstępne. Najpierw na taśmie należy zapisać słowo wejściowe, do którego zostanie zastosowany program. Słowo wejściowe to końcowa sekwencja znaków zapisanych w sąsiednich komórkach taśmy; wewnątrz słowa wejściowego nie powinno być pustych komórek, a tylko puste komórki powinny znajdować się po jego lewej i prawej stronie. Puste słowo wejściowe oznacza, że wszystkie komórki na taśmie są puste. Po drugie, należy ustawić automat w stan q 1 (wskazywany jako pierwszy w tabeli) i umieścić go pod pierwszym symbolem słowa wejściowego: abbq 1 Jeśli słowo wejściowe jest puste, automat może patrzeć na dowolną komórkę , bo wszystkie są puste. Po tych wstępnych krokach rozpoczyna się wykonywanie programu. W tabeli znajduje się komórka na przecięciu pierwszego wiersza (ponieważ automat jest w stanie q 1) i kolumny odpowiadającej pierwszemu znakowi słowa wejściowego (niekoniecznie jest to lewa kolumna tabeli), i cykl wskazany w tej komórce jest wykonywany. W efekcie maszyna będzie w nowej konfiguracji. Teraz te same czynności są powtarzane, ale dla nowej konfiguracji: w tabeli znajduje się komórka odpowiadająca stanowi i symbolowi tej konfiguracji i z tej komórki wykonywany jest cykl. Itp. Kiedy program się kończy? Wprowadźmy pojęcie cyklu stop. Jest to cykl, który niczego nie zmienia: automat wpisuje do widocznej komórki ten sam symbol, co w niej wcześniej, nie porusza się i pozostaje w tym samym stanie, tj. to jest cykl S,N,q dla konfiguracji
6 2) Drugi wynik jest „zły”: wtedy pętle MT zapętlają się, nigdy nie dochodząc do cyklu zatrzymania (na przykład automat przesuwa się w prawo przy każdym kroku i dlatego nie może się zatrzymać, ponieważ taśma nie ma końca). W tym przypadku mówi się, że MT nie ma zastosowania do danego słowa wejściowego. Nie może być mowy o jakimkolwiek wyniku z takim wynikiem. Zauważ, że ten sam algorytm (program MT) może mieć zastosowanie do niektórych słów wejściowych (tj. stop) i nie ma zastosowania do innych (tj. pętla). Zatem stosowalność/niestosowalność zależy nie tylko od samego algorytmu, ale także od słowa wejściowego. Na jakich słowach wejściowych algorytm powinien się zatrzymać? Na, że tak powiem, dobre słowa, czyli na tych, które odnoszą się do dopuszczalnych danych początkowych rozwiązywanego problemu, dla którego problem ma znaczenie. Ale na taśmie można nagrać dowolne słowa wejściowe, w tym te, dla których zadanie nie ma sensu; na takich słowach zachowanie algorytmu nie jest ustalone, może się zatrzymać (dla dowolnego wyniku) lub może działać cyklicznie. Konwencje skracania nagrania Uzgodnijmy kilka konwencji skracania nagrania programu dla MT. 1) Jeżeli widoczny symbol nie zmienia się w takcie, albo automat się nie porusza, albo stan automatu się nie zmienia, to nic nie zapiszemy w odpowiedniej pozycji taktu. Na przykład podczas konfiguracji
7 1.2 Przykłady programowania MT Przyjrzyjmy się przykładom programowania MT, aby zademonstrować kilka typowych technik programowania MT. Aby skrócić sformułowanie problemów, wprowadzamy dwie następujące konwencje: słowo wejściowe będziemy oznaczać literą P; litera A będzie oznaczać alfabet słowa wejściowego, tj. zbiór tych symboli, z których i tylko z których może składać się P (należy jednak zauważyć, że w słowach pośrednich i wyjściowych mogą występować inne symbole). Przykład 1 (przesuwanie automatu, zastępowanie znaków) A=(0,1,2,3,4,5,6,7,8,9). Niech P będzie słowem niepustym; więc P jest ciągiem cyfr dziesiętnych, tj. notacja nieujemnej liczby całkowitej w systemie dziesiętnym. Wymagane jest nagranie na taśmę zapisu o liczbie o 1 większej od liczby P. Rozwiązanie. Aby rozwiązać ten problem, proponuje się wykonanie następujących czynności: 1. Przesuń maszynę na ostatnią cyfrę numeru. 2. Jeśli jest to liczba od 0 do 8, zastąp ją kolejną liczbą 1 i zatrzymaj się; na przykład: Jeśli jest to liczba 9, zamień ją na 0 i przesuń automat na poprzednią cyfrę, a następnie zwiększ tę przedostatnią cyfrę o 1 w ten sam sposób; np.: Przypadek szczególny: P ma tylko dziewiątki (np. 99). Wtedy automat przesunie się w lewo, zastępując dziewiątki zerami, a na końcu znajdzie się pod pustą komórką. Wpisz 1 w tę pustą komórkę i zatrzymaj się (odpowiedź będzie wynosić 100): W postaci programu dla MT akcje te są opisane następująco: Λ q1 0,R,q1 1,R,q1 2,R,q1 3 ,R,q1 4, R,q1 5,R,q1 6,R,q1 7,R,q1 8,R,q1 9,R,q1 ,L,q2 q2 1,N,! 2,N! 3,N! 4,N! 5,N! 6,N! 7,N! 8,N! 9,N! 0,L,q2 1,N,! Wyjaśnienia. q1 to stan, w którym automat „przebiega” pod ostatnią cyfrą liczby. Aby to zrobić, nieustannie przesuwa się w prawo, nie zmieniając widocznych liczb i pozostając w tym samym stanie. Ale jest jedna cecha: gdy maszyna ma mniej niż 7
8 to ostatnia cyfra, wtedy jeszcze o tym nie wie (przecież nie widzi co jest napisane w sąsiednich komórkach) i ustali to dopiero gdy trafi do pustej komórki. Dlatego po dojściu do pierwszej pustej komórki automat wraca pod ostatnią cyfrę i przechodzi do stanu q2 (nie trzeba już przesuwać się w prawo). q2 to stan, w którym automat dodaje 1 do cyfry, którą w danej chwili widzi. Najpierw jest to ostatnia cyfra liczby; jeśli jest w zakresie od 0 do 8, to maszyna zastępuje ją cyfrą o 1 większą i zatrzymuje się. Ale jeśli jest to liczba 9, to automat zastępuje ją 0 i przesuwa się w lewo, pozostając w stanie q2. W ten sposób doda teraz 1 do poprzedniej cyfry. Jeśli ta cyfra jest również równa 9, to automat zastępuje ją 0 i przesuwa się w lewo, pozostając w stanie q2 jak poprzednio, ponieważ powinien wykonać tę samą akcję zwiększenie o 1 widoczną cyfrę. Jeżeli automat przesunął się w lewo, a w widocznej komórce nie ma numeru (ale jest „puste”), to wpisuje tu 1 i zatrzymuje się. Zauważ, że dla pustego słowa wejściowego nasz problem nie jest zdefiniowany, dlatego na tym słowie MT może zachowywać się w dowolny sposób. W naszym programie na przykład przy pustym słowie wejściowym MT zatrzymuje się i daje odpowiedź 1. Powyżej podaliśmy program w pełnej, nieskróconej postaci. Napiszmy teraz program w skróconej, bardziej wizualnej formie, natomiast po prawej stronie pokrótce wyjaśnimy czynności, które są realizowane w odpowiednich stanach automatu: Λ q1,r,r,r,r,r,r ,r,r,r,r, l,q2 pod ostatnią cyfrą q2 1,! 2! 3! 4,! 5,! 6! 7! osiem,! 9,! 0,L, 1,! widoczna liczba + 1 Tak będziemy pisać programy w przyszłości. Przykład 2 (analiza postaci) A=(a,b,c). Przenieś pierwszy znak niepustego słowa P na jego koniec. Na przykład: a b c b b c b a Rozwiązanie. Aby rozwiązać ten problem, proponuje się wykonać następujące czynności: 1. Zapamiętaj pierwszy znak słowa P, a następnie usuń ten znak. 2. Przesuń automat w prawo pod pierwszą pustą komórką po P i wpisz w nią zapamiętany symbol. Jak „uciec” w prawo wiemy już z poprzedniego przykładu. Ale jak zapamiętać pierwszą postać? Rzeczywiście, w MT nie ma innego urządzenia do przechowywania danych poza taśmą i nie ma sensu zapamiętywać symbolu w jakiejś komórce na taśmie: gdy tylko automat przesunie się na lewo lub na prawo od tej komórki, natychmiast zapomina o tym symbolu . Co robić? Wyjściem tutaj jest użycie różnych stanów automatu. Jeżeli pierwszym znakiem jest a, to musisz przejść do stanu q2, w którym automat 8
9 biegnie w prawo i pisze na końcu. Jeśli symbol b był pierwszy, to należy przejść do stanu q3, gdzie wszystko odbywa się tak samo, tylko symbol b jest napisany na końcu. Jeżeli pierwszym symbolem był c, to przechodzimy do stanu q4, w którym automat dołącza symbol c po słowie wejściowym. Dlatego naprawiamy pierwszy symbol, przenosząc automat do różnych stanów. Jest to typowa technika programowania MT. W związku z powyższym program będzie wyglądał następująco: abc q1 ,R,q2 ,R,q3 ,R,q4,R, analiza pierwszego znaku, usunięcie go, rozgałęzienie q2,r,r , r, a ,! zapisz a po prawej q3,r,r,r, b,! zapisz b po prawej q4,r,r,r, c,! napisz c po prawej Rozważ zachowanie tego programu na słowach wejściowych zawierających co najwyżej jeden znak. Z pustym słowem, które jest „złe” dla zadania, program zapętli automat, będąc w stanie q1 i spadając cały czas na puste komórki, przesunie się w prawo w nieskończoność. (Oczywiście w tym przypadku program mógłby zostać zatrzymany, ale specjalnie zrobiliśmy pętlę, aby zademonstrować tę możliwość.) Jeśli w słowie wejściowym jest dokładnie jeden znak, to automat usunie ten znak, przeniesie jedną komórkę do w prawo i wpisz w nim ten znak: cc q1 q4! W ten sposób słowo jednego znaku po prostu przesunie się o jedną komórkę w prawo. To jest do przyjęcia. W końcu komórki taśmy nie są ponumerowane, więc położenie słowa na taśmie nie jest w żaden sposób ustalone, a ruchu słowa w lewo lub w prawo nie można zauważyć. W związku z tym nie jest wymagane, aby słowo wyjściowe znajdowało się w tym samym miejscu, w którym znajdowało się słowo wejściowe, wynik może znajdować się zarówno po lewej, jak i po prawej stronie tego miejsca. Przykład 3 (porównanie znaków, wymazywanie słów) A=(a,b,c). Jeśli pierwszy i ostatni symbol (niepustego) słowa P są takie same, to słowo to nie jest zmieniane, w przeciwnym razie jest zastępowane pustym słowem. Rozwiązanie. Aby rozwiązać ten problem, proponuje się wykonać następujące czynności: 1. Zapamiętaj pierwszy znak słowa wejściowego bez jego wymazywania. 2. Przesuń automat pod ostatni znak i porównaj go z zapamiętanym. Jeśli są równe, nie rób nic więcej. 3. W przeciwnym razie zniszcz całe słowo wejściowe. Wiemy już, jak zapamiętać znak i jak wyprzedzić maszynę do ostatniego znaku wyrazu z poprzednich przykładów. Zaimplementowano kasowanie słowa wejściowego 9
10, zastępując wszystkie jego symbole symbolem Λ. Jednocześnie, ponieważ automat znajduje się na końcu słowa, przeniesiemy automat z prawej strony na lewą do pierwszej pustej komórki. Akcje te opisuje następujący program dla MT (przypomnij sobie, że krzyżyk w komórce tabeli oznacza, że odpowiednia konfiguracja nie może pojawić się podczas wykonywania programu): a b c Λ q1,q2,q4,q6,! analiza pierwszego znaku, rozgałęzienia q2,r,r,r, L,q3 przejdź do ostatniego znaku na pierwszym znaku a q3,!, q8, q8 porównaj jako ostatni. znak z a nie jest równy na q8 (wymazywanie P) q4,r,r,r, L,q5 podobnie dla pierwszego znaku b q5, q8,!, q8 q6,r,r,r, L,q7 podobnie dla pierwszego znaku c q7, q8, q8,! q8 ,L, ,L, ,L,! kasuj całe słowo, przesuwając się od prawej do lewej Przykład 4 (usuwanie znaku ze słowa) A=(a,b). Usuń ze słowa P jego drugi znak, jeśli taki istnieje. Rozwiązanie. Wydawałoby się, że ten problem jest łatwy do rozwiązania: trzeba przesunąć automat pod komórkę z drugim symbolem, a następnie wyczyścić tę komórkę: a b b a a b b a a b a Przypominamy jednak, że w słowie wyjściowym nie powinno być pustych komórek. Dlatego po usunięciu drugiego znaku konieczne jest „skompresowanie” słowa poprzez przesunięcie pierwszego znaku o jedną komórkę w prawo. Aby to zrobić, automat musi wrócić do pierwszego symbolu, zapamiętać go i wymazać, a następnie, ponownie przesuwając się w prawo, wpisać go do komórki, w której był drugi symbol. Jednak początkowy „spacer” w prawo do drugiego symbolu, aby go wymazać, a następnie powrót do pierwszego symbolu są niepotrzebnymi czynnościami: jaka różnica polega na przeniesieniu pierwszego symbolu do pustej komórki lub do komórki z jakimś symbol? Dlatego od razu zapamiętujemy pierwszy znak, wymazujemy go i zapisujemy zamiast drugiego: abbabbaaba W postaci programu dla MT wszystko to jest zapisane w następujący sposób: ab Λ q1 Λ,R,q2 Λ,R, q3,! parsowanie i usuwanie pierwszego znaku, rozgałęzianie q2,! a! a! zamiana drugiego znaku na q3 b,!,! b! zamiana drugiego znaku na b Przykład 5 (kompresja słów) A=(a,b,c). Usuń ze słowa P pierwsze wystąpienie znaku a, jeśli występuje. Rozwiązanie. W poprzednim przykładzie przesunęliśmy tylko jeden znak na pozycję w prawo - 10
11 tyg. W tym przykładzie wykonamy pętlę w prawo, aby przenieść wszystkie początkowe znaki b i c słowa wejściowego do pierwszego znaku a lub do pustej komórki: bcbcbaabbaabcaabcba czy ten symbol y można przenieść do prawej komórki? Jeżeli qx oznacza stan, w którym konieczne jest wpisanie do widocznej komórki symbolu x, który znajdował się poprzednio w komórce po lewej stronie, to czynność tę można przedstawić w następujący sposób: najpierw symbol x pobrany z komórki na lewa jest zapisana w widocznej komórce; po drugie, automat przesuwa się w prawo pod komórkę, w której konieczne będzie wtedy wpisanie właśnie zastąpionego symbolu y; po trzecie automat przechodzi do stanu q y, w którym dokona tego zapisu. Powtarzanie takich taktów w cyklu spowoduje przesunięcie w prawo o jedną pozycję początkowych znaków słowa wejściowego. Cykl ten powinien zakończyć się, gdy w następnej komórce pojawi się znak a lub Λ (y=a lub y=λ), a na początku cyklu możemy założyć, że znak „pusty” (x=λ) zostaje przeniesiony do miejsce pierwszego znaku po lewej stronie. Wynikiem jest następujący program dla MT: a b c Λ q1 Λ,R,! ,R,q2 ,R,q3,! q Λ : usuń pierwszy znak i przesuń go w prawo q2 b,!,r, b,r,q3 b,! q b: napisz b, przesuń widoczny wcześniej znak w prawo q3 c,! c,r,q2,r, c,! q c: napisz c, przesuń poprzednio widoczny znak w prawo W tym programie należy zwrócić uwagę na cykl Λ,R,!
12 pierwszy znak (nie można go jeszcze usunąć w starym miejscu), a następnie, wracając na stare miejsce, wpisz znak a: bcabcabbcabaca Przesunięcie znaku o jedną pozycję w lewo jest podobne do przesunięcia znaku w prawo, jak omówiono w poprzednich dwóch przykładach, więc podamy program dla MT bez dodatkowych komentarzy. Zauważmy tylko, że w stanach q2, q3 i q4 automat widzi tylko pustą komórkę, aw stanie q5 koniecznie widzi pierwszy symbol słowa wejściowego, ale nie pustą komórkę. a b c € q1,l,q2,l,q3,l,q4,! przeanalizuj pierwszy znak by przesunąć go w lewo q2 a,r,q5 przypisz a do lewej q3 b,r,q5 przypisz b do lewej q4 c,r,q5 przypisz c do lewej q5,! a! a! zastąp pierwszy pierwszy znak przykładem 7 (rozprzestrzenianie słów) А=(a,b,c). Wstaw znak a w słowie P po pierwszym wystąpieniu znaku c, jeśli występuje. Rozwiązanie. Przeglądamy słowo wejściowe od lewej do prawej do pustej komórki lub do pierwszego znaku c. W pierwszym przypadku c nie jest zawarte w P, więc nic nie robimy. W drugim przypadku trzeba zrobić miejsce na wstawiony znak a, dla którego przesuwamy początek słowa P (od pierwszego znaku do znalezionego znaku c) o jedną pozycję w lewo. W tym przypadku wykonujemy takie przesunięcie od prawej do lewej od symbolu c na początek słowa, ponieważ automat znajduje się pod tym symbolem. Ponadto, aby później nie wracać na zwolnioną pozycję, rozpoczynamy to przesunięcie od wpisania a zamiast znalezionego znaku c. Ponieważ to cykliczne przesunięcie w lewo jest zaimplementowane podobnie jak cykliczne przesunięcie w prawo z Przykładu 5, nie będziemy tego wyjaśniać, ale od razu podamy program dla MT: abc Λ q1,r,r, a,l,q4,l ,! w prawo do c, wstaw a zamiast c, przesuń c w lewo q2,l, a,l,q3 a,l,q4 a,! przesuń a w prawo q3 b,l,q2,l, b,l,q4 b,! przesunięcie w prawo b q4 c,l,q2 c,l,q3,l, c,! przenieś c w prawo Przykład 8 (tworzenie słowa w nowym miejscu) А=(a, b, c). Usuń z P wszystkie wystąpienia znaku a. Rozwiązanie. Poprzednie przykłady pokazują, że wstawianie znaków do słów i usuwanie znaków ze słów jest w MT dość trudne. Dlatego czasami łatwiej jest nie rozszerzać ani kompresować słowa wejściowego, ale tworzyć słowo wyjściowe.
13 w innym, wolnym miejscu na taśmie. Właśnie to zrobimy, aby rozwiązać ten problem. W szczególności proponuje się wykonanie następujących czynności: 1. Zbudujemy słowo wyjściowe po prawej stronie słowa wejściowego. Aby rozgraniczyć te słowa, oddzielamy je jakimś symbolem pomocniczym, na przykład znakiem =, innym niż wszystkie symbole alfabetu A (patrz krok 1). (Przypomnij sobie, że na taśmie można zapisać nie tylko znaki z alfabetu słowa wejściowego.) 2. Następnie wracamy do początku słowa wejściowego (patrz krok 2). a b c a b c = a b c = Teraz naszym zadaniem jest przeniesienie w pętli wszystkich znaków słowa wejściowego, z wyjątkiem a, na prawo za znakiem = do wygenerowanego słowa wyjściowego. W tym celu analizujemy pierwszy znak słowa wejściowego. Jeśli to a, usuń go i przejdź do następnego znaku (patrz krok 3). Jeśli pierwszym znakiem jest b lub c, to usuwamy go i „biegamy” w prawo do pierwszej pustej komórki (patrz krok 4), gdzie wpisujemy ten znak (patrz krok 5). b c = c = c = b Wracamy ponownie w lewo do znaku, który stał się pierwszym w słowie wejściowym i powtarzamy te same czynności, ale w odniesieniu do tego znaku (patrz kroki 6-9). c = b = b = b c Ta pętla kończy się, gdy wrócimy w lewo i zobaczymy = jako pierwszy znak. Jest to znak, że całkowicie przeskanowaliśmy słowo wejściowe i przenieśliśmy wszystkie jego znaki inne niż a do słowa wyjściowego utworzonego po prawej stronie. Konieczne jest skasowanie tego znaku, przejście w prawo pod słowem wyjściowym i zatrzymanie (patrz krok 10). = b c b c 9 10 Biorąc pod uwagę wszystko, co zostało powiedziane, budujemy program dla MT. Jednocześnie zauważamy, że oprócz symboli a, b i c, w trakcie rozwiązywania problemu na taśmie pojawia się znak =, więc w tabeli musi być również kolumna na ten znak. abc = Λ q1,r,r,r, =,q2 wpisz znak = q2,l,l,l,l,r,q3 od prawej do pierwszego symbolu słowa q3 Λ,R, Λ,R, q4 , R,q5 Λ,R,! przeanalizuj i usuń, gałąź q4,r,r,r,r, b,q2 napisz b po prawej, wróć na lewo (w pętlę) q5,r,r,r,r, c,q2 napisz c do w prawo, powrót w lewo (w cyklu) 13
14 Przykład 9 (zamocowanie miejsca na taśmie) A=(a,b). Podwój słowo P, umieszczając między nim a jego kopią znak =. Na przykład: a a b a b = a a b Rozwiązanie. Ten problem jest rozwiązywany podobnie jak poprzedni: wpisujemy znak = na końcu słowa wejściowego, następnie wracamy na początek słowa i kopiujemy wszystkie jego znaki (w tym a) w pętli do pustych komórek po prawej stronie : aabaab = aab = aab = a 1 2 Jednak jest też różnica: skopiowane znaki słowa wejściowego nie są usuwane, co prowadzi do następującego problemu. Po wpisaniu kopii następnego znaku po prawej, musimy wrócić do słowa wejściowego na pozycji tego znaku, a następnie przejść w prawo do następnego znaku, aby już go skopiować. Ale skąd wiesz, do której pozycji słowa wejściowego wrócić? Na przykład, skąd wiemy w naszym przykładzie, że po skopiowaniu pierwszego znaku a powinniśmy wrócić dokładnie do pierwszego znaku słowa wejściowego, a nie do drugiego lub trzeciego? W poprzednim zadaniu zawsze wracaliśmy do pierwszego z pozostałych znaków słowa wejściowego, a teraz zapisujemy wszystkie znaki, więc nie jest jasne, które znaki już skopiowaliśmy, a które jeszcze nie. Zauważamy również, że w MT komórki taśmy nie są w żaden sposób ponumerowane, w MT nie ma liczników, które pozwoliłyby nam określić, ile znaków już skopiowaliśmy. Ogólnie rzecz biorąc, problem, przed którym stoimy, jest następujący: jak naprawić na taśmie pewną pozycję, w której już byliśmy i do której musimy wrócić później? Zwykle ten problem jest rozwiązywany w ten sposób. Gdy znajdujemy się w tej pozycji po raz pierwszy, zastępujemy znajdujący się w niej znak jego sobowtórem nowym symbolem pomocniczym, a różne znaki zastępujemy różnymi sobowtórami, na przykład a na A i b na B. Następnie, niektóre czynności wykonujemy w innych miejscach na taśmie. Aby potem wrócić do naszej pozycji, wystarczy znaleźć na taśmie komórkę, w której znajduje się symbol A lub B. Następnie w tej komórce można przywrócić poprzedni symbol, jeśli nie potrzebujemy już naprawiać tej pozycji (było to przywrócić poprzedni symbol, który musieliśmy zastąpić różnymi symbolami na różne odpowiedniki). Wykorzystajmy tę technikę w naszym zadaniu, wykonując następujące czynności: 1. Jak już wspomniano, najpierw wpisujemy znak = za słowem wejściowym (patrz krok 1 powyżej). 2. Następnie wracamy pod pierwszy znak słowa wejściowego (patrz krok 2 powyżej). 3. Następnie zastępujemy widoczny symbol a podwójnym A (patrz krok 3 poniżej), „biegamy” w prawo do pierwszej wolnej komórki i wpisujemy do niej symbol a (patrz krok 4). Następnie wracamy w lewo do celi z podwójnym A (patrz ryc. krok 5), przywróć poprzedni znak a i przejdź w prawo do następnego znaku (patrz krok 6). 14
15 aab = A ab = A ab = a A ab = aaab = aa A b = aa A b = aaaa B = aabaab = aab Teraz skopiuj drugi znak w ten sam sposób (zastąp go A, dodaj a na końcu, itd.) ) i wszystkie kolejne znaki słowa wejściowego. 4. Gdy skopiujemy ostatni znak słowa wejściowego i wrócimy do jego bliźniaka (po kroku 12), to po przesunięciu o jedną pozycję w prawo dojdziemy do znaku = (krok 13). Jest to sygnał, że słowo wejściowe zostało całkowicie skopiowane, więc praca MT musi zostać zakończona. Biorąc pod uwagę wszystko, co zostało powiedziane, otrzymujemy następujący program dla MT: ab = AB Λ q1,r,r, =,L,q2 put = na prawo od słowa q2,l,l,r,q3 to po lewej pod pierwszym znakiem q3 A,R, q4 B,R,q5,! analiza i zamiana następnego znaku q4,r,r,r, a,q6 wpisz a po prawej q5,r,r,r, b,q6 wpisz b po prawej q6,l,l,l, a,r ,q3 b,r, q3 powrót, powrót do następnego. Zauważmy, że w tym programie możemy pozbyć się stanu q6 łącząc go ze stanem q2, pod warunkiem, że q2 powróci w lewo zarówno do pustej komórki, jak i do symboli A i B: ab = AB Λ.. q2,l,l ,l, a,r,q3 b,r,q3,r,q3 od lewej do Λ, A lub B Zadania do samodzielnego rozwiązania Uwagi: 1) W zadaniach brane są pod uwagę tylko nieujemne liczby całkowite, chyba że stwierdzono inaczej. 2) Przez system „pojedynczych” liczb rozumie się rejestrację nieujemnej liczby całkowitej za pomocą patyczków, przy czym należy wypisać tyle patyków, ile wynosi liczba; np.: 2, 5, 0<пустое слово>. 1,1 A=(a,b,c). Przypisz symbol b (P bp) po lewej stronie słowa P. 1.2 A=(a,b,c). Przypisz symbole bc (P Pbc) po prawej stronie słowa P. 1,3 A=(a,b,c). Zmień na co drugi znak w słowie s. 15
16 1,4 A=(a,b,c). Pozostaw tylko pierwszy znak w słowie P (nie zmieniaj pustego słowa). 1,5A=(a,b,c). Pozostaw tylko ostatni znak w słowie P (nie zmieniaj pustego słowa). 1,6 A=(a,b,c). Określ, czy P jest słowem ab. Odpowiedź (słowo wyjściowe): słowo ab, jeśli jest, lub puste słowo w przeciwnym razie. 1,7 A=(a,b,c). Sprawdź, czy słowo P zawiera znak a. Odpowiedź: słowo jednego znaku a (tak, w zestawie) lub puste słowo (nie). 1,8 A=(a,b,c). Jeśli słowo P nie zawiera symbolu a, zamień wszystkie symbole b w P na c, w przeciwnym razie podaj słowo z jednego symbolu a jako odpowiedź. 1,9 A=(a,b,0,1). Określ, czy słowo P jest identyfikatorem (niepuste słowo zaczynające się na literę). Odpowiedź: słowo a (tak) lub puste słowo (nie) A=(a,b,0,1). Określ, czy słowo P jest reprezentacją liczby w notacji binarnej (niepuste słowo składające się tylko z cyfr 0 i 1). Odpowiedź: słowo 1 (tak) lub słowo A=(0,1). Traktując niepuste słowo P jako reprezentację liczby binarnej, usuń z niego nieznaczne zera, jeśli są takie A=(0,1). Dla niepustego słowa P określ, czy jest to reprezentacja potęgi dwójki (1, 2, 4, 8,) w systemie liczb binarnych. Odpowiedź: słowo 1 (jest) lub słowo A=(0,1,2,3). Biorąc pod uwagę, że niepuste słowo P reprezentuje liczbę w czwartorzędowym systemie liczbowym, określ, czy jest to liczba parzysta, czy nie. Odpowiedź: 1 (tak) lub A=(0.1). Biorąc pod uwagę niepuste słowo P jako reprezentację liczby w systemie binarnym, uzyskaj liczbę binarną równą czterokrotności liczby P (na przykład: A=(0,1). Rozpatrując niepuste słowo P jako reprezentację liczby w systemie binarnym, otrzymaj liczbę binarną równą niepełnemu ilorazowi dzielenia liczby P przez 2 (na przykład:) A=(a,b,c). Jeśli P jest słowem o parzystej długości (0, 2, 4,), to zwróć odpowiedź a, w przeciwnym razie puste słowo A=(0,1,2). Rozważając niepuste słowo P jako reprezentację liczby w trójskładnikowym systemie liczbowym, określ, czy jest to liczba parzysta, czy nie. Odpowiedź: 1 (tak) lub 0. (Uwaga: parzysta trójka musi mieć parzystą liczbę cyfr 1.) 1,18 A=(a,b,c). Niech P będzie nieparzystej długości. Zostaw tylko środkowy symbol A=(a,b,c) w P. Jeśli słowo P ma parzystą długość, zostaw w nim tylko lewą połowę A=(a,b,c). Przypisz po lewej stronie niepustego słowa P jego pierwszy znak. szesnaście
17 1,21 A=(a,b). W przypadku niepustego słowa P ustal, czy jego pierwszy znak ponownie je wprowadzi. Odpowiedź: a (tak) lub puste słowo A=(a,b). W niepustym słowie P zamień jego pierwszy i ostatni symbol A=(a,b). Ustal, czy P jest palindromem (zmiennym, symetrycznym słowem), czy nie. Odpowiedź: a (tak) lub puste słowo A=(a,b). Zamień w P każde wystąpienie a przez bb A=(a,b,c). Zamień w P każde wystąpienie ab na c A=(a,b). Podwój słowo P (na przykład: abb abbabb) A=(a,b). Podwój każdy znak słowa P (np. bab bbaabb) A=(a,b). Odwróć słowo P (na przykład: abb bba) A=(0,1). Traktując niepuste słowo P jako liczbę binarną, uzyskaj tę samą liczbę, ale w systemie czwartorzędowym. (Uwaga: weź pod uwagę, że w liczbie binarnej może występować nieparzysta liczba cyfr.) 1,30 A=(0,1,2,3). Rozważając niepuste słowo P jako reprezentację liczby w czwartorzędowym systemie liczbowym, otrzymaj reprezentację tej liczby w systemie binarnym A=(0,1,2). Biorąc pod uwagę niepuste słowo P jako liczbę dodatnią w notacji trójskładnikowej, zmniejsz tę liczbę o A=( ). Biorąc pod uwagę słowo P jako reprezentację liczby w systemie jednostek liczbowych, uzyskaj reprezentację tej liczby w systemie trójskładnikowym. (Rekomendacja: należy wyjmować patyczek z „pojedynczej” liczby w cyklu i za każdym razem dodawać 1 do liczby trójkowej, która jako pierwsza jest ustawiona na 0.) 1,33 A=(0,1,2). Rozpatrując niepuste słowo P jako reprezentację liczby w trójskładnikowym systemie liczbowym, uzyskaj reprezentację tej liczby w systemie jednostek.Niech słowo P ma następującą postać: (...(...nm gdzie znaki +, /, lub, po lewej stronie których zaznaczono n drążków , a po prawej stronie m. Wykonaj odpowiednią operację w systemie numerów jednostek (w odpowiedzi podaj słowo wskazane po prawej stronie strzałki): a) dodawanie: (... + (... (... (n 0, m 0) nm n+ mb) odejmowanie): (... (... (... (nm 0) nmnm c) mnożenie) : (... (... (... (n 0, m 0) nmnm d) dzielenie całkowite: ((... /... (... (n 0, m>0, k=n) div m) nmk e) biorąc resztę: (... (... (... (n 0, m>0, k=n mod m) nmk 17)
18 f) maksymalna: (... (... (... (n 0, m 0, k=max(n, m)) nmk g) minimalna: (... (... (... (n 0, m 0, k=min(n,m)) knm 1,35 A=( ) Zakładając, że słowo P reprezentuje liczbę w systemie tożsamości, ustal, czy ta liczba jest potęgą 3 (1, 3, 9 , 27,) Odpowiedź: słowo puste, jeśli tak, lub słowo z jednego patyka inaczej A=( ) Biorąc pod uwagę słowo P jako reprezentację liczby n w systemie tożsamości, otrzymujemy liczbę 2 n A=( ) w tym samym systemie Niech słowo P będzie reprezentacją liczby 2 n (n=0, 1, 2,) w systemie tożsamościowym Pobierz liczbę n w tym samym systemie Niech P będzie postaci Q+R, gdzie Q i R są niepustymi słowami symboli 0, 1 i 2. Traktując Q i R jako liczby notacji w trójskładnikowym systemie liczbowym (ewentualnie z nieznacznymi zerami), podaj jako odpowiedź zapis sumy tych liczb w ten sam system trójkowy jako zapis liczb w trójskładnikowym systemie liczbowym (ewentualnie z nieznacznymi zerami) i zakładając, że QR, podaj jako odpowiedź zapis różnicy tych liczb w tym w tym samym systemie trójskładnikowym.Niech P ma postać Q=R, gdzie Q i R są dowolnymi słowami z symboli a i b. Podaj odpowiedź a, jeśli słowa Q i R są takie same, a puste słowo inaczej. Niech P będzie postaci Q=R, gdzie Q i R są niepustymi słowami symboli 0 i 1. Traktowanie Q i R jako zapis liczb binarnych (ewentualnie z zerami nieznaczącymi), odpowiedź na słowo 1, jeśli te liczby są równe, a słowo 0 w przeciwnym razie Niech P będzie mieć postać Q>R, gdzie Q i R są niepustymi słowami symboli 0 i 1 zer), podaj słowo 1 jako odpowiedź, jeśli liczba Q jest większa od liczby R, a słowo 0 w przeciwnym razie A=((,)). Sprawdź, czy słowo P jest zrównoważone w nawiasach. Odpowiedź: D (tak) lub N (nie) A=(a,b). Jeśli w P jest więcej znaków a niż znaków b, zwróć odpowiedź a, jeśli znaki a są mniejsze niż znaki b, zwróć odpowiedź b, w przeciwnym razie zwróć puste słowo. 2. Normalne algorytmy Markowa W tej sekcji rozważymy problem pisania normalnych algorytmów Markowa. Podano krótki opis tych algorytmów, wyjaśniono na przykładach główne metody ich kompilacji oraz zaproponowano problemy do samodzielnego rozwiązania. osiemnaście
19 2.1 Krótki opis normalnych algorytmów podstawienia Markowa Interesującą cechą normalnych algorytmów Markowa (NAM) jest to, że używają one tylko jednej operacji elementarnej, tzw. podstawienia, która jest zdefiniowana w następujący sposób. Formuła podstawienia to zapis postaci α β (czytaj „zamień α na β”), gdzie α i β to dowolne słowa (prawdopodobnie puste). W tym przypadku α nazywa się lewą stroną wzoru, a β prawą stroną. Samo podstawienie (jako działanie) jest określone przez wzór podstawienia i stosowane do jakiegoś słowa P. Istotą operacji jest to, że w słowie P znajduje się część, która pasuje do lewej strony tego wzoru (tzn. z α) , i jest zastępowany przez formuły po prawej stronie (czyli na β). W tym przypadku pozostałe części słowa P (na lewo i na prawo od α) nie ulegają zmianie. Otrzymane słowo R nazywamy wynikiem podstawienia. Konwencjonalnie można to przedstawić w następujący sposób: P x α y R x β y Niezbędne wyjaśnienia: 1. Jeśli lewa strona wzoru podstawienia jest zawarta w słowie P, to mówią, że ten wzór ma zastosowanie do P. Ale jeśli α nie jest zawarte w P, to wzór jest uważany za nie mający zastosowania do P i nie wykonuje się podstawienia. 2. Jeżeli lewa strona α występuje w P kilka razy, to z definicji tylko pierwsze wystąpienie α w P jest zastępowane prawą stroną β: P x α y α z R x β y α z 3. Jeśli prawa strona wzoru na podstawienie jest pustym słowem , wtedy podstawienie α sprowadza się do usunięcia części α z P (na marginesie zauważamy, że nie jest zwyczajowo oznaczać puste słowo we wzorach na podstawienie): P x α y R xy 4. Jeżeli po lewej stronie wzoru na podstawienie wskazano puste słowo, to podstawienie β sprowadza się z definicji do przypisania β po lewej stronie słowu P: P x R β x Z tej zasady wynika bardzo ważny fakt : formuła z pustą lewą stroną ma zastosowanie do dowolnego słowa. Zauważ też, że formuła z pustą lewą i prawą stroną nie zmienia słowa. Definicja NAM Normalny algorytm Markowa (NAM) jest niepustym uporządkowanym zbiorem formuł podstawienia: 19
20 α1 β1 α 2 β 2... (k 1) α k β k W tych wzorach można stosować dwa rodzaje strzałek: strzałkę regularną () i strzałkę z ogonkiem (a). Formuła ze zwykłą strzałką nazywana jest formułą zwykłą, a formuła ze strzałką w kształcie ogona jest nazywana formułą końcową. Różnica między nimi została wyjaśniona poniżej. Napisanie algorytmu w postaci NAM oznacza przedstawienie takiego zestawu formuł. Reguły wykonywania NAM Przede wszystkim podano jakieś słowo wejściowe P. Tam, gdzie dokładnie jest napisane, nie ma znaczenia, to pytanie nie jest określone w NAM. Praca NAM sprowadza się do realizacji sekwencji kroków. Na każdym kroku formuły podstawienia zawarte w NAM są skanowane od góry do dołu i wybierana jest pierwsza z formuł mających zastosowanie do słowa wejściowego P, tj. najwyższy z nich, którego lewa część jest zawarta w R. Następnie dokonuje się podstawienia według znalezionego wzoru. Uzyskuje się nowe słowo P. W następnym kroku to słowo P jest traktowane jako słowo oryginalne i stosuje się do niego tę samą procedurę, tj. wzory są przeszukiwane ponownie od góry do dołu, zaczynając od najwyższego i przeszukiwana jest pierwsza formuła odnosząca się do słowa P, po czym następuje odpowiednie podstawienie i otrzymuje się nowe słowo P. I tak dalej: Р Р Р Na szczególną uwagę zasługuje fakt, że na każdym etapie formuły w USA są zawsze oglądane od pierwszego. Niezbędne wyjaśnienia: 1. Jeśli w następnym kroku zastosowano zwykłą formułę (α β), praca nad NAM jest kontynuowana. 2. Jeżeli ostateczna formuła (α a β) została zastosowana w kolejnym kroku, to po jej zastosowaniu praca NAM zostaje zatrzymana. Słowo, które w tym momencie wyszło, jest słowem wyjściowym, tj. wynik zastosowania NAM do słowa wejściowego. Jak widać, różnica między zwykłą i ostateczną formułą podstawienia przejawia się tylko w tym, że po zastosowaniu zwykłej formuły praca NAM jest kontynuowana, a po końcowej formule zatrzymuje się. 3. Jeżeli w następnym kroku żadna formuła nie ma zastosowania do bieżącego słowa, to w tym przypadku praca NAM również zostaje zakończona, a bieżące słowo jest uważane za słowo wyjściowe. W ten sposób NAM zatrzymuje się z dwóch powodów: albo zastosowano ostateczną formułę, albo żadna z formuł nie pasuje. Oba są uważane za „dobre” zakończenia NAM. W obu przypadkach mówi się, że NAM odnosi się do słowa wejściowego. dwadzieścia
Moskiewski Uniwersytet Państwowy im. M.V. Łomonosowa Wydział Matematyki Obliczeniowej i Cybernetyki V.N. Pilszczikow, W.G. Abramow, AA Vylitok, I.V. Maszyna Hot Turinga i algorytmy Markowa.
MASZYNA TURINGA W BADANIACH TEORII ALGORYTMÓW Lebedeva N.Yu. Shuya Oddział Iwanowskiego Uniwersytetu Państwowego MASZYNA TURINGOWA W BADANIA TEORII ALGORYTMÓW Lebedeva N. Yu. Oddział Shuya
DODAWANIE Dodanie 1 do liczby oznacza otrzymanie liczby następującej po podanej: 4+1=5, 1+1=14 itd. Dodanie cyfr 5 oznacza trzykrotne dodanie od 1 do 5: 5+1+1+1=5+=8. ODEJMOWANIE Odejmij 1 od liczby oznacza
Problemy i rozwiązania rundy kwalifikacyjnej Olimpiady DM&T 2014-2015 Wszystkie problemy, manipulatory i rozwiązania są dostępne dla uczestników na stronie internetowej Olimpiady. Wszystkie zaproponowane zadania zostały ocenione z taką samą liczbą punktów. Liczy się.
Maszyna Turinga 1 Maszyna Turinga jest pojęciem matematycznym, a nie prawdziwą maszyną obliczeniową. MT to matematyczny model urządzenia obliczeniowego. MT został zaproponowany przez Alana Turinga w 1936 r.
Rozwiązywanie problemów z maszyną Turinga online >>> Rozwiązywanie problemów z maszyną Turinga online Rozwiązywanie problemów z maszyną Turinga online Zawartość komórki może się zmienić, możesz wpisać do niej inny znak lub ją usunąć
Systemy liczbowe W naszych czasach człowiek stale ma do czynienia z liczbami. Od dzieciństwa wszyscy znamy ogólnie przyjętą notację liczb za pomocą cyfr arabskich. Jednak ta metoda rejestracji nie była powszechnie stosowana.
Zaimplementowany algorytm Używamy następującej odmiany algorytmu Euklidesa do obliczenia gcd liczb M i N:. aM, bN; 2. t a-b, jeśli t = 0, zatrzymaj się; 3. a t, b min(a,b), przejdź do kroku 2. Po zatrzymaniu GCD(M,N)
Zadania eliminacyjne Olimpiady z Matematyki Dyskretnej i Informatyki Teoretycznej z rozwiązaniami (przy rozwiązywaniu konstruktywnych zadań uczestnik pracuje z emulatorami, w rozwiązaniach są pokazane zdjęcia ich interfejsów)
Rozdział B. Lekcja arytmetyki komputerowej B3. Arytmetyka binarna Zobaczmy, jak sobie poradziłeś z ćwiczeniami z lekcji B2. Oto ich rozwiązania. Ćwiczenia B2-2 a) Tabela rozmieszczenia kettlebell wygląda tak: ponumerowane
Lekcja 23 W warunkach zadania M, x oznaczają odpowiednio opis maszyny Turinga i słowo wejściowe w formacie wprowadzonym na wykładzie (i zapisanym w wersji roboczej podręcznika). Problem 23.1. Udowodnij to
Sekcja 6. Teoria algorytmów. Nieformalne pojęcie algorytmu, jego główne cechy i właściwości. Alfabet, słowa, algorytm w alfabecie. Całkiem równoważne algorytmy. Definicja normalnego algorytmu (algorytmu
SYSTEMY LICZBY POZYCYJNEJ Istnieje wiele sposobów przedstawiania liczb. W każdym razie liczba jest reprezentowana przez symbol lub grupę symboli (słowo) jakiegoś alfabetu. Nazwiemy takie symbole
Zadania do klasy 11 Etap selekcji. Pierwsza runda 1. Kodowanie informacji. Systemy liczbowe (2 punkty) [Permutacje] Ile jest trzycyfrowych liczb szesnastkowych, które będą jednocześnie?
Rozwiązywanie zadań na temat "Reprezentacja liczb w komputerze" Rodzaje zadań: 1. Liczby całkowite. Reprezentowanie liczb w formacie stałoprzecinkowym. 2. Liczby ułamkowe. Reprezentacja liczb w formacie zmiennoprzecinkowym.
1. Rycerze i łotrzykowie. Schemat logiczny - 1. Zadania i rozwiązania pełnej rundy Olimpiady Dmitri-2017-2018 Przy okrągłym stole siedzą cztery osoby. Każdy z nich jest rycerzem lub waletem. Rycerze zawsze mówią tylko
Systemy liczbowe System liczbowy to sposób pisania liczb przy użyciu określonego zestawu znaków specjalnych (liczb). W technice komputerowej stosuje się systemy liczb pozycyjnych, w których wartość cyfry
WYKŁAD 3. Algorytmy przetwarzania tablic jednowymiarowych. Cel wykładu: Zapoznanie z pojęciem tablicy. Nabycie umiejętności budowania algorytmów do przetwarzania tablic jednowymiarowych. 6. Algorytmy
Wersja demonstracyjna zadania 6 USE 2019 Wejściową wartością algorytmu jest liczba naturalna N. Algorytm buduje z niej nową liczbę R w następujący sposób. 1) Konstruuje się zapis binarny liczby N. 2) Do tego zapisu
Wprowadzenie do systemów liczbowych A.A. Sztabka System liczbowy to sposób pisania liczb przy użyciu danego zestawu znaków specjalnych (liczb). Istnieją pozycyjne i niepozycyjne systemy liczbowe. W niepozycyjnym
Część III Języki, gramatyki, automaty 137 Rozdział 10 Języki i automaty skończone 10.1 Język Dicka Jak wiemy, prawidłowe struktury nawiasów są wyliczane za pomocą liczb katalońskich. Wypisujemy wszystkie poprawne nawiasy
Miejski etap Ogólnorosyjskiej Olimpiady Uczniów z Informatyki Moskwa, 00 grudnia. Zadania dla klas 7-8 Każde zadanie ocenia się na 0 punktów. Ostateczny wynik ustalany jest jako suma punktów za zadania
Maszyny wirtualne Wprowadzenie Ponad czterdzieści lat temu wybitny amerykański matematyk Emil L. Post opublikował w Journal of Symbolic Logic artykuł „Finite combinatorial process, formulacja!” (jej
Ugra Fizyka i Matematyka Liceum VP Czuwakow Zadanie C6 (Teoria liczb na jednolitym egzaminie państwowym) Przewodnik edukacyjny i metodologiczny Chanty-Mansyjsk 0 VP Czuwakow Problem C6 (Teoria liczb na jednolitym egzaminie państwowym): Przewodnik, - Chanty-Mansyjsk,
9 KLASA 1. W jednej z komór nieskończonej kratki znajduje się robot, któremu można wydać następujące komendy: góra (robot przechodzi od góry do następnej komórki); w dół (robot porusza się do
Systemy liczbowe System liczbowy to sposób pisania liczb przy użyciu określonego zestawu znaków specjalnych (cyfr). Istnieją pozycyjne i niepozycyjne systemy liczbowe. W systemach niepozycyjnych waga
Systemy liczbowe System liczbowy to sposób opisywania liczb za pomocą znaków określonego alfabetu według znanych zasad. Systemy liczb pozycyjnych W systemie liczb pozycyjnych wartość cyfry zależy
K. Polyakov, 009-06 6- (poziom podstawowy, czas 4 min) Temat: Znalezienie algorytmu minimalnej długości dla wykonawcy. Co musisz wiedzieć: wykonawcą jest osoba, grupa ludzi, zwierzę, maszyna lub inny przedmiot,
Wykład 5 Podstawy reprezentacji informacji w automatach cyfrowych Pozycyjne systemy liczbowe System liczbowy jest zbiorem technik i reguł pisania liczb w znakach cyfrowych. Wszelkie zamierzone
Elementy teorii złożoności Maszyna Turinga Alan Turing (23.06.1912-7.06.1954) (Alan Mathison Turing) Angielski matematyk, logik, kryptograf. W 1936 zaproponował abstrakcyjną obliczeniową „Maszynę Turinga”,
Ministerstwo Edukacji i Nauki Federacji Rosyjskiej Państwowa Instytucja Edukacyjna Edukacji Zawodowej Federacji Rosyjskiej „Rostowski Uniwersytet Państwowy” M. E. Abramyan
10 KLASA 1. Liczby rzeczywiste spełniają następujące relacje: Znajdź wszystkie możliwe trójki liczb, gdzie Rozwiązanie. Zauważ, że oznaczając i odejmując te równości od siebie, otrzymujemy Załóż, że wszystkie
Dodatek do artykułu Gorbunov K.Yu., Lyubetsky V.A. „Algorytm liniowy minimalnej restrukturyzacji struktur” Dowód Lematu 3. Blok sztywny, ograniczony z obu stron wspólnymi genami, nazywamy półsztywnym
Dodatek 1 Warsztaty do rozdziału 2 „Reprezentacja informacji w komputerze” Praca praktyczna do paragrafu 2.1 Przykład 2.1. Wyraź liczby 2466,675 10, 1011,11 2 jako potęgi podstawy
Korespondencja Liceum Fizyczne i Matematyczne „Avangard” EN Filatov ALGEBRA 8 Podręcznik eksperymentalny Część 1 MOSKWA 2016 SPIS TREŚCI 1. Podzielność. 2. Parzysty nieparzysty 3. Sety. 4. Zabawne zadania. 5. Kombinatoryka
Zeszyt zadań z informatyki ucznia (tsy) 11. klasy fizycznej i matematycznej gimnazjum 36 Włodzimierza Część II 2016-2017 2 1. Algorytmizacja. 1.1 Pewna operacja jest proponowana na dwóch dowolnych
Temat 7. Reprezentacja informacji w komputerze Jednostki informacji. Bit - (cyfra bit-biry - cyfra binarna) najmniejsza jednostka informacji - ilość informacji potrzebna do rozróżnienia dwóch równie prawdopodobnych zdarzeń.
I. V. Jakowlew Materiały matematyczne MathUs.ru Spis treści Zapis dziesiętny 1 Ogólnorosyjska Olimpiada dla uczniów z matematyki ........ 1 2 Moskiewska Olimpiada Matematyczna......... ....... ........
Temat 1: Układy równań liniowych A. Ya Ovsyannikov Ural Federal University Instytut Matematyki i Informatyki Wydział Algebry i Matematyki Dyskretnej Algebra i geometria dla fizyków-inżynierów
Rozdział 5 Elementy teorii algorytmów 31 Wyjaśnienie pojęcia algorytmu Słowa kluczowe: algorytm teoria algorytmów uniwersalny wykonawca Maszyna Turinga Postmaszyna normalna Algorytm Markowa Dlaczego
Rozwiązywanie problemów na temat „Reprezentacja liczb w komputerze”. Typy zadań. 1. Liczby całkowite. Reprezentowanie liczb w formacie stałoprzecinkowym. 2. Liczby ułamkowe. Reprezentowanie liczb w formacie zmiennoprzecinkowym
A. Shen Gry i strategie z punktu widzenia matematyki, MTsNMO Proste gry i klasyfikacja pozycji Na stole jest 12 meczów. Gracze na zmianę rozgrywają od jednego do trzech meczów. Kto nie może wykonać ruchu
Teoria algorytmów 79 3.2. Algorytmy normalne j Niech A będzie alfabetem bez symboli. oraz. Zwykła formuła podstawienia jest reprezentacją postaci P Q, gdzie P i Q to niektóre słowa w alfabecie A. Ostatnia
WYKŁAD 2. Algorytmy struktur cyklicznych. Cel wykładu: Zapoznanie z pojęciem algorytmu struktury cyklicznej. Nabycie umiejętności konstruowania algorytmów dla struktury cyklicznej. 5. Algorytmy cykliczności
Wykłady z matematyki. Wydanie. TMM-1 J. W. Czebrakow TEORIA MACIERZY MAGII St. Petersburg, 2010 technika
Praktyczna praca. Formy reprezentacji informacji liczbowych na komputerze. Część I. Systemy liczbowe. System liczbowy to sposób reprezentowania dowolnej liczby za pomocą jakiegoś alfabetu
Moskiewski Instytut Fizyki i Technologii Wydział Innowacji i Zaawansowanych Technologii Logika matematyczna i Teoria Algorytmów, jesień 2018 Seminarium 1: język do pisania formalnych stwierdzeń, z rozwiązaniami niektórych
Wykład 16
16 (wysoki poziom, czas min) Temat: Numery kodowania. Systemy liczbowe. Co musisz wiedzieć: zasady kodowania liczb w systemach liczb pozycyjnych w celu przetłumaczenia liczby, powiedzmy 15, z systemu
2015 Wyrażenia regularne Rozwiązania problemów rundy kwalifikacyjnej (dwie opcje) Wariant 1 Zbuduj wyrażenie regularne opisujące zbiór słów z liter a i b, z których wszystkie słowa określone przez wyrażenie regularne
