Automaty abstrakcyjne maszyna Turinga

Wykład nr 3 z Podstaw InformatykiMaszyna Turinga

Abstrakcyjna maszyna zdolna wykonywać algorytmy (Alan Mathison Turing - On Com-putable Numbers, 1936) Obecnie stosowana głównie do udowadnia­nia nierozstrzygalności problemów matema­tycznychElementy tworzące maszynę Turinga

• Nieskończenie długa taśma podzielona na pola (z zapisanymi w nich symbolami)

• Ruchoma głowica czytająco-pisząca znajdu jąca się w jednym z m możliwych stanów wewnętrznych

Program dla maszyny Turinga

• Aktualny stan maszyny S_r = ( s., q.)

• s symbol na taśmie pod głowicą

• q wewnętrzny stan głowicy

• Ruch maszyny R_y = ( s_k, K, q,)

• s_k nowy symbol zapisany na taśmie

• K kierunek ruchu głowicy

• q, nowy wewnętrzny stan głowicy

• Program to zbiór reguł (rozkazów) postaci R. = T( S_r) zwany tablicą charakterystycznąTablica charakterystyczna

Twierdzenie Turinga

• Każdy algorytm może być realizowany przez odpowiednio zaprogramowaną maszynę Tu­ringa

Przykład 1

• Na taśmie zapisano 3-literowy ciąg złożony z symboli: a, b i c.

• Tylko napis abcjest poprawny

• Podać algorytm rozpoznawania tego napisuPrzykład 1 - algorytm

1. Pobierz symbol. Jeżeli jest nim a to przejdź do 2, w przeciwnym przypadku przejdź do 4.

2. Przesuń głowicę w prawo, pobierz symbol, jeżeli jest nim b to przejdź do 3, jeśli nie

- przejdź do 4.

3. Przesuń głowicę w prawo, pobierz symbol, jeżeli jest nim c to przejdź do 5, jeśli nie

- przejdź do 4.

4. Sygnalizuj nieprawidłowy napis. Koniec.

5. Sygnalizuj napis prawidłowy. Koniec.Przykład 1 - tablica charaktery­styczna

Przykład 1 - algorytm

Przykład 1 - algorytm

Przykład 1 - algorytm

Przykład 1 - algorytm

Przykład 1 - algorytm

Przykład 1 - algorytm

Automat kończy pracę w stanie q₄.

Napis niepoprawny

Przykład 1 - algorytm

Przykład 1 - algorytm

Przykład 1 - algorytm

Przykład 1 - algorytm

Przykład 1 - algorytm

Przykład 1 - algorytm

Przykład 1 - algorytm

Przykład 1 - algorytm

Automat kończy pracę w stanie q₅.

Napis poprawny

Przykład 2 - inkrementacja liczby

Algorytm inkrementacji liczb binar­nych

• Przesuwaj się od prawej do lewej i zamieniaj wszystkie jedynki na zera aż do napotkania zera, które należy zamienić na jedynkę

• Dodatkowo sprawdzaj czy zamienione na jedynkę zero nie było bitem znaku. Jeśli tak rozszerz liczbę o nowy bit znaku.Przykład 2 - tablica charaktery­styczna

Stan q_i - poszukiwanie najmniej znaczącego bitu liczby

Przykład 2 - tablica charaktery­styczna

Stan q₂ - zamiana jedynek na zera aż do napo­tkania zera i zamiana go na jedynkę

Przykład 2 - tablica charaktery­styczna

Stan q - sprawdzenie czy nie zmieniono zna-

o

ku liczby

Przykład 2 - tablica charaktery­styczna

Stan q₄ - stan końcowy

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 2 - tablica charaktery­styczna

Przykład 3 - obliczanie wartości

bezwzgiędnej liczby

• Na taśmie umieszczono liczbę całkowitą ze znakiem zapisaną w zapisie uzupełnienio­wym do 2

• W miejsce tej liczby wpisać jej wartość bez­względną

• Głowica znajduje się na lewo od liczby na

symbolu pustym (DPrzykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkęPrzykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Np. + 11Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Np.-11 11110101Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Przykład 3 - algorytm

1. Czy liczba na taśmie jest liczbą nieujemną ? Jeżeli tak - STOP, jeśli nie - idź do 2

2. Oblicz liczbę przeciwną:

1. Zaneguj wszystkie bity liczby

2. Dodaj jedynkę

Każdy fragment algorytmu można zrealizować niezależnie a potem połączyć uzyskane roz­wiązania w jedno. Założenie: głowica z lewej strony liczbyPrzykład 3 - testowanie bitu znaku

Przykład 3 - negowanie bitów

Przykład 3 - inkrementacja

Przykład 3 - całe zadanie

Przykład 3 - całe zadanie

Przykład 3 - całe zadanie

Przykład 3 - całe zadanie

Negowanie bitów

Przykład 3 - całe zadanie

Przykład 3 - całe zadanie

Inkrementacja liczby

Przykład 3 - całe zadanie

Podsumowanie

• Elementy tworzące maszynę Turinga

• Tablica charakterystyczna jako zapis pro­gramu dla maszyny Turinga

• Przykłady algorytmów i zaprogramowania ich na maszynie Turinga

• Twierdzenie Turinga o realizowalności algo rytmów

---