Maszyna Turinga

Z Wikipedii

Maszyna Turinga to stworzony przez Alana Turinga abstrakcyjny model komputera służący do wykonywania algorytmów. Każdy algorytm wyrażalny na maszynie Turinga można wyrazić w rachunku lambda i odwrotnie. Ponieważ jednak maszyny Turinga rozszerza się bardzo trudno, zaś rachunek lambda bardzo łatwo, w praktyce są one o wiele mniej popularne jako rzeczywiste modele obliczeń. Są za to używane często do udowadniania nierozstrzygalności różnych problemów.

Maszyna Turinga składa się z nieskończenie długiej taśmy podzielonej na pola. Taśma może być nieskończona jednostronnie lub obustronnie. Każde pole może znajdować się w jednym z N stanów. Maszyna zawsze jest ustawiona nad jednym z pól i znajduje się w jednym z M stanów. Zależnie od kombinacji stanu maszyny i pola maszyna zapisuje nową wartość w polu, zmienia stan, a następnie może przesunąć się o jedno pole w prawo lub w lewo. Taka operacja nazywana jest rozkazem. Maszyna Turinga jest sterowana listą zawierającą dowolną ilość takich rozkazów. Liczby N i M mogą być dowolne, byle skończone. Czasem dopuszcza się też stan (M+1)-szy, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej program.

Maszyna posiadająca zdolność wykonywania dowolnego programu jest nazywana uniwersalną maszyna Turinga. Praktyczną realizacją uniwersalnej Maszyny Turinga jest komputer.

Można rozważać bardzo wiele różnych wariantów maszyny Turinga. Na przykład nie ma potrzeby pozwalać na pozostanie maszyny na tym samym polu, ponieważ maszyna musi albo zakończyć obliczenia przez zapętlenie, albo po nie więcej niż N*M krokach dane pole opuścić i wystarczy wtedy przyjąć dla danej kombinacji początkowej stany podczas opuszczania pola.

Istnieją też maszyny Turinga wielotaśmowe lub niedeterministyczne (gdzie jednej parze (symbol, stan) może odpowiadać kilka instrukcji) oraz wielowymiarowe (prostą dwuwymiarową maszyną Turinga jest mrówka Langtona).

Spis treści 1 Zapis formalny 2 Przykładowa Maszyna Turinga 3 Przykład działania maszyny Turinga 3.1 ΦabaΦ 3.2 ΦabbΦ 4 Zobacz też

[edytuj] Zapis formalny

Formalnie Maszynę Turinga opisuje się poprzez siódemkę:

MT = < Q, Σ, δ, Γ, q₀, B, F >

gdzie:

Q - skończony zbiór stanów

q₀ - stan początkowy, q₀ ∈ Q

F - zbiór stanów końcowych

Γ - skończony zbiór dopuszczalnych symboli

B - symbol pusty, B ∈ Γ

Σ - zbiór symboli wejściowych - podzbiór zbioru Γ nie zawierający B

δ - funkcja opisana następująco:

→

co oznacza że jest to funkcja pobierająca aktualny stan maszyny oraz symbol wejściowy a dającą w wyniku symbol jaki ma się pojawić na taśmie, kolejny stan maszyny oraz przesunięcie głowicy maszyny (lewo, prawo lub bez przesunięcia).

[edytuj] Przykładowa Maszyna Turinga

Zaprezentowano tutaj tabelę stanów reprezentującą przykładową Maszynę Turinga. Ta Maszyna ma za zadanie podwajanie znaków w podanym ciągu,

np. ciąg wejściowy ΦabcΦ (gdzie Φ to symbol pusty oznaczający koniec danych) zamieni na ΦaabbccΦ

Q = { q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇, q₈, q₉, q₁₀, q₁₁, q₁₂ }

q₀ = q₀

F = { q₁₂ }

Γ = { Φ, a, b, c }

B = Φ

Σ = { a, b, c }

Σ+B\Q

q0

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

Φ

q12 -,-

q2 Φ,P

q3 a,P

q4 a,L

q5 Φ,L

q0 Φ,P

q7 Φ,P

q8 b,P

q4 b,L

q10 Φ,P

q11 c,P

q4 c,L

s t a n b i e r n y

a

q1 Φ,P

q1 a,P

q2 a,P

q12 -,-

q4 a,L

q5 a,L

q6 a,P

q7 a,P

q12 -,-

q9 a,P

q10 a,P

q12 -,-

b

q6 Φ,P

q1 b,P

q2 b,P

q12 -,-

q4 b,L

q5 b,L

q6 b,P

q7 b,P

q12 -,-

q9 b,P

q10 b,P

q12 -,-

c

q9 Φ,P

q1 c,P

q2 c,P

q12 -,-

q4 c,L

q5 c,L

q6 c,P

q7 c,P

q12 -,-

q10 c,P

q9 c,P

q12 -,-

Kolumny tabeli są to elementy zbioru Q - dopuszczalne stany Maszyny Turinga, wiersze oznaczają kolejno wszystkie dopuszczalne symbole wejściowe (podczas wejścia w dany stan głowica czytająca Maszyny Turinga odczytuje aktualny symbol z taśmy i to jest właśnie jeden z tych symboli). Każda komórka tabeli zawiera w sobie instrukcje dla Maszyny Turinga, a mianowicie dla przykładu:

q2 a,P

q₂ - oznacza kolejny stan, w którym znajdzie się maszyna po przejściu z aktualnego stanu

a - symbol, który zostanie umieszczony na tym polu taśmy

P - przesunięcie głowicy maszyny (L - w lewo o jedno pole, P - w prawo o jedno pole, - - brak przesunięcia głowicy)

[edytuj] Przykład działania maszyny Turinga

Weźmy znacznie prostszą maszynę Turinga niż w przykładzie powyżej - sprawdzającą, czy dane słowo jest palindromem.

Q = { q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇}

q₀ = q₀

F = { q₆, q₇ }

Γ = { Φ, a, b }

B = Φ

Σ = { a, b }

	q0	q1	q2	q3	q4	q5	q6	q7
Φ	q6 -,-	q3 Φ,L	q4 Φ,L	q6 -,-	q6 -,-	q0 Φ,P	TAK	NIE
a	q1 Φ,P	q1 a,P	q2 a,P	q5 Φ,L	q7 -,-	q5 a,L
b	q2 Φ,P	q1 b,P	q2 b,P	q7 -,-	q5 Φ,L	q5 b,L

[edytuj] ΦabaΦ

 ¡q0
ΦabaΦ

  ¡q1
ΦΦbaΦ

   ¡q1
ΦΦbaΦ

   ¡q1
ΦΦbaΦ

    ¡q1
ΦΦbaΦ

   ¡q3
ΦΦbaΦ

  ¡q5
ΦΦbΦΦ

 ¡q5
ΦΦbΦΦ

  ¡q0
ΦΦbΦΦ

   ¡q2
ΦΦΦΦΦ

  ¡q4
ΦΦΦΦΦ

  ¡q6 TAK
ΦΦΦΦΦ

[edytuj] ΦabbΦ

 ¡q0
ΦabbΦ

  ¡q1
ΦΦbbΦ

   ¡q1
ΦΦbbΦ

    ¡q1
ΦΦbbΦ

   ¡q3
ΦΦbbΦ

   ¡q7 NIE
ΦΦbbΦ

[edytuj] Zobacz też

• Maszyna RAM
• przegląd zagadnień z zakresu matematyki
• Busy Beaver
• funkcja rekurencyjna
• problem Collatza