Maszyna Turinga: Różnice pomiędzy wersjami

Usunięte 5835 bajtów ,  4 lata temu
m
-przykłady (są i tak bez źródeł, a słabo sformatowane i abstrakcyjne, a także bez omówienia)
(poprawa linku)
m (-przykłady (są i tak bez źródeł, a słabo sformatowane i abstrakcyjne, a także bez omówienia))
{{dopracować|źródła=2017-08}}
[[Plik:Turing Machine.png|thumb|Artystyczna wizja maszyny Turinga]]
[[Plik:Turing machine 2b.svg|thumb|Grafika przedstawiająca maszynę Turinga w stanie q<sub>1</sub> nad zerem na taśmie]]
:: <math>\delta : \Gamma \times Q \rightarrow Q \times \Gamma \times \{ L, P, - \}</math>
:: 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).
 
== Przykłady maszyny Turinga ==
=== Podwajanie znaków ===
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<sub>0</sub>, q<sub>1</sub>, q<sub>2</sub>, q<sub>3</sub>, q<sub>4</sub>, q<sub>5</sub>, q<sub>6</sub>, q<sub>7</sub>, q<sub>8</sub>, q<sub>9</sub>, q<sub>10</sub>, q<sub>11</sub>, q<sub>12</sub>}
: q<sub>0</sub> = q<sub>0</sub>
: F = {q<sub>12</sub>}
: Γ = {Φ, a, b, c}
: B = Φ
: Σ = {a, b, c}
 
<center>
{| class="wikitable"
! <sub>Σ+B</sub>\<sup>Q</sup>
! q<sub>0</sub>
! q<sub>1</sub>
! q<sub>2</sub>
! q<sub>3</sub>
! q<sub>4</sub>
! q<sub>5</sub>
! q<sub>6</sub>
! q<sub>7</sub>
! q<sub>8</sub>
! q<sub>9</sub>
! q<sub>10</sub>
! q<sub>11</sub>
! q<sub>12</sub>
|-
! Φ
| q<sub>12</sub><br />-,-
| q<sub>2</sub><br />Φ,P
| q<sub>3</sub><br />a,P
| q<sub>4</sub><br />a,L
| q<sub>5</sub><br />Φ,L
| q<sub>0</sub><br />Φ,P
| q<sub>7</sub><br />Φ,P
| q<sub>8</sub><br />b,P
| q<sub>4</sub><br />b,L
| q<sub>10</sub><br />Φ,P
| q<sub>11</sub><br />c,P
| q<sub>4</sub><br />c,L
|rowspan=4| s t a n<br />b i e r n y
|-
! a
| q<sub>1</sub><br />Φ,P
| q<sub>1</sub><br />a,P
| q<sub>2</sub><br />a,P
| q<sub>12</sub><br />-,-
| q<sub>4</sub><br />a,L
| q<sub>5</sub><br />a,L
| q<sub>6</sub><br />a,P
| q<sub>7</sub><br />a,P
| q<sub>12</sub><br />-,-
| q<sub>9</sub><br />a,P
| q<sub>10</sub><br />a,P
| q<sub>12</sub><br />-,-
|-
! b
| q<sub>6</sub><br />Φ,P
| q<sub>1</sub><br />b,P
| q<sub>2</sub><br />b,P
| q<sub>12</sub><br />-,-
| q<sub>4</sub><br />b,L
| q<sub>5</sub><br />b,L
| q<sub>6</sub><br />b,P
| q<sub>7</sub><br />b,P
| q<sub>12</sub><br />-,-
| q<sub>9</sub><br />b,P
| q<sub>10</sub><br />b,P
| q<sub>12</sub><br />-,-
|-
! c
| q<sub>9</sub><br />Φ,P
| q<sub>1</sub><br />c,P
| q<sub>2</sub><br />c,P
| q<sub>12</sub><br />-,-
| q<sub>4</sub><br />c,L
| q<sub>5</sub><br />c,L
| q<sub>6</sub><br />c,P
| q<sub>7</sub><br />c,P
| q<sub>12</sub><br />-,-
| q<sub>10</sub><br />c,P
| q<sub>9</sub><br />c,P
| q<sub>12</sub><br />-,-
|}
</center>
 
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:
<center>
{| class="wikitable"
| q<sub>2</sub><br />a,P
|}
</center>
 
: q<sub>2</sub> – 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)
 
=== Sprawdzanie palindromów ===
Weźmy znacznie prostszą maszynę Turinga niż w przykładzie powyżej – będzie sprawdzać, czy dane słowo jest [[palindrom]]em.
 
: Q = {q<sub>0</sub>, q<sub>1</sub>, q<sub>2</sub>, q<sub>3</sub>, q<sub>4</sub>, q<sub>5</sub>, q<sub>6</sub>, q<sub>7</sub>}
: q<sub>0</sub> = q<sub>0</sub>
: F = {q<sub>6</sub>, q<sub>7</sub>}
: Γ = {Φ, a, b}
: B = Φ
: Σ = {a, b}
 
{| class="wikitable"
!
! q<sub>0</sub>
! q<sub>1</sub>
! q<sub>2</sub>
! q<sub>3</sub>
! q<sub>4</sub>
! q<sub>5</sub>
! q<sub>6</sub>
! q<sub>7</sub>
|-
! Φ
| q<sub>6</sub><br />-,-
| q<sub>3</sub><br />Φ,L
| q<sub>4</sub><br />Φ,L
| q<sub>6</sub><br />-,-
| q<sub>6</sub><br />-,-
| q<sub>0</sub><br />Φ,P
| rowspan="3"| TAK
| rowspan="3"| NIE
|-
! a
| q<sub>1</sub><br />Φ,P
| q<sub>1</sub><br />a,P
| q<sub>2</sub><br />a,P
| q<sub>5</sub><br />Φ,L
| q<sub>7</sub><br />-,-
| q<sub>5</sub><br />a,L
|-
! b
| q<sub>2</sub><br />Φ,P
| q<sub>1</sub><br />b,P
| q<sub>2</sub><br />b,P
| q<sub>7</sub><br />-,-
| q<sub>5</sub><br />Φ,L
| q<sub>5</sub><br />b,L
|}
 
{{dopracować|format}}
 
==== Działanie dla ΦabaΦ ====
¡q<sub>0</sub>
ΦabaΦ
 
¡q<sub>1</sub>
ΦΦbaΦ
 
¡q<sub>1</sub>
ΦΦbaΦ
 
¡q<sub>1</sub>
ΦΦbaΦ
 
¡q<sub>1</sub>
ΦΦbaΦ
 
¡q<sub>3</sub>
ΦΦbaΦ
 
¡q<sub>5</sub>
ΦΦbΦΦ
 
¡q<sub>5</sub>
ΦΦbΦΦ
 
¡q<sub>0</sub>
ΦΦbΦΦ
 
¡q<sub>2</sub>
ΦΦΦΦΦ
 
¡q<sub>4</sub>
ΦΦΦΦΦ
 
¡q<sub>6</sub> TAK
ΦΦΦΦΦ
 
==== Działanie dla ΦabbΦ ====
¡q<sub>0</sub>
ΦabbΦ
 
¡q<sub>1</sub>
ΦΦbbΦ
 
¡q<sub>1</sub>
ΦΦbbΦ
 
¡q<sub>1</sub>
ΦΦbbΦ
 
¡q<sub>3</sub>
ΦΦbbΦ
 
¡q<sub>7</sub> NIE
ΦΦbbΦ
 
=== Negowanie w kodzie U2 ===
Poniższy schemat przedstawia algorytm negowania liczby w [[Kod uzupełnień do dwóch|kodzie U2]]. Zapis 0→1L należy interpretować: zamień 0 na 1 i przesuń głowicę w lewo<br />
[[Plik:Turing machine negU2.svg|center|500px|Algorytm negowania liczby w kodzie [[Kod uzupełnień do dwóch|U2]]]]
Przykład odwracania liczby -8 przy pomocy algorytmu opisanego powyższym diagramem:
 
Zapis (I,J;0→1L) oznacza
* wykonano przejście pomiędzy stanami I i J
* zmieniono 0 na 1 na pozycji głowicy
* przesunięto głowicę w lewo
 
Spis przejść wraz ze stanem taśmy, nawiasy prostokątne wskazują położenie głowicy.
0. [#]#1000#
1. (A,A;#→#R) #[#]1000#
2. (A,A;#→#R) ##[1]000#
3. (A,B;1→0R) ##0[0]00#
4. (B,B;0→1R) ##01[0]0#
5. (B,B;0→1R) ##011[0]#
6. (B,B;0→1R) ##0111[#]
7. (B,C;#→#L) ##011[1]#
8. (C,C;1→0L) ##01[1]0#
9. (C,C;1→0L) ##0[1]00#
10. (C,C;1→0L) ##[0]000#
11. (C,D;0→1L) #[#]1000#
12. (D,E;#→0L) [#]01000# (uzupełnienie wiodącego zera, nie można odwrócić -8 w U2 na 4 bitach)
 
W 12. kroku osiągany jest stan E, co kończy program. Na taśmie znajduje się napis 01000, co odpowiada liczbie 8 w kodzie U2.
 
== Inne ujęcie ==
96 250

edycji