Maszyna Turinga: Różnice pomiędzy wersjami

Dodane 120 bajtów ,  2 lata temu
m
bardziej matematyczny zapis formalny, poprawki estetyczne
(→‎Linki zewnętrzne: linki zewnętrzne)
m (bardziej matematyczny zapis formalny, poprawki estetyczne)
Formalnie Maszynę Turinga opisuje się poprzez [[krotka (struktura danych)|krotkę]]:
 
<center><font size="+1"><math>MT = < Q, Σ\Sigma, δ\delta, Γ\Gamma, q<sub>0</sub>q_0, B, F ></math></font></center>
 
gdzie:
: <math>Q</math> – skończony [[zbiór]] stanów
: q<submath>0q_0 \in Q</submath> – [[stan obiektu (informatyka)|stan]] początkowy, q<sub>0</sub> ∈ Q
: <math>F</math> – zbiór stanów końcowych
: Γ<math>\Gamma</math> – skończony zbiór dopuszczalnych symboli
: <math>B \in \Gamma</math> – [[symbol]] pusty, B ∈ Γ
: Σ<math>\Sigma</math> – zbiór symboli wejściowych – [[podzbiór]] zbioru Γ<math>\Gamma</math>, do którego nie należy <math>B</math>
: δ<math>\delta</math> – [[funkcja]] opisana następująco:
:: <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).
 
6

edycji