Maszyna Turinga: Różnice pomiędzy wersjami

{{Definicja|Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej "głowicy"„głowicy”, wykonującej proste operacje na zapisanych na taśmie wartościach.}}

[[Plik:Turing Machine.png|thumb|right|Artystyczna wizja maszyny Turinga]]

'''Maszyna Turinga''' -– stworzony przez [[Alan Turing|Alana Turinga]] abstrakcyjny model [[komputer]]a służącego do wykonywania [[algorytm]]ów, składającego 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 [[rozkaz]]em. Maszyna Turinga jest sterowana listą zawierającą dowolną liczbę takich rozkazów. Liczby N i M mogą być dowolne, byle skończone. Czasem dopuszcza się też stan M+1, który oznacza zakończenie pracy maszyny. Lista rozkazów dla maszyny Turinga może być traktowana jako jej [[Oprogramowanie|program]].

== Wstęp ==

W informatyce dowodzi się równoważności wielu różnych wariantów maszyny Turinga. Np. dość łatwo jest pokazać, że maszyna Turinga z wieloma taśmami nie różni się istotnie od klasycznej maszyny jednotaśmowej. Również niedeterministyczne maszyny Turinga są równoważne deterministycznym. Rozważania na temat mocy obliczeniowej niedeterministycznych maszyn Turinga są podstawą centralnego problemu [[Złożoność obliczeniowa|teorii złożoności obliczeniowej]] – "P„P versus NP"NP”.

Mimo że maszyna Turinga jest abstrakcją o dużej mocy obliczeniowej (większej na przykład niż dowolny komputer), istnieje wiele problemów (np. [[problem stopu]]), których nie da się na niej rozwiązać. Matematycy rozważają więc (od czasów samego [[Alan Mathison Turing|Turinga]]) silniejsze modele obliczeń, które mogą takim zadaniom podołać. Hipotetyczne maszyny potrafiące wykonywać takie obliczenia, nazywa się [[hiperkomputer]]ami. Należy zauważyć, że przy obecnym stanie wiedzy nie jest jasne, czy prawa fizyki rządzące naszym światem pozwalają na skonstruowanie maszyn obliczeniowych silniejszych niż maszyna Turinga. Jest to pole aktywnych prac badawczych.

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

: F = { q₁₂ }

: Γ = { Φ, a, b, c }

: Σ = { a, b, c }

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

: F = { q₆, q₇ }

: Γ = { Φ, a, b }

: Σ = { a, b }

| rowspan="3" | TAK

| rowspan="3" | NIE

0. [#]#1000#

Model przedstawiony przez [[Roger Penrose|Rogera Penrose'aPenrose’a]] w ''Nowym umyśle cesarza'' (s. 46-93, ISBN 83-01-11819-9, str. 46-93) jest nieco inny, bardziej oszczędny, chociaż równoważny matematycznie.

Przyjmuje się, że maszyna obsługuje tylko dwa znaki na taśmie – zero i jedynkę. Przy tym stany wewnętrzne są oznaczone [[dwójkowy system dwójkowyliczbowy|liczbami dwójkowymi]] i maszyna zaczyna od stanu 0. Maszyna po każdej operacji zmienia stan wewnętrzny, znak na taśmie i przesuwa się w lewo lub w prawo. Może też się zatrzymać. Reguły oznacza się przez odpowiedni zestaw przejść, np. (ostatnia cyfra oznacza znak na taśmie i jest wytłuszczona dla czytelności)

Jest to maszyna '''UN+1''' zwiększająca liczbę zapisaną w [[Jedynkowy system jedynkowyliczbowy|systemie jedynkowym]] o jeden, czyli dopisująca na końcu pierwszego ciągu jedynek na taśmie jeszcze jedną jedynkę.

T₇: 0'''0''' → 0'''0'''R, 0'''1''' → ???,

Większość jest niekompletna (bywa np. ,<!-- POPRAW TO MIEJSCE! --> że zawierają więcej, niż cztery jedynki z rzędu, czyli są ''niepoprawnie określone'') lub nigdy się nie zatrzymuje, zdarzają się też powtórzenia. Żaden system kodowania nie pozwala wyeliminować wszystkich takich dat.

* [http://edu.i-lo.tarnow.pl/inf/prg/003_mt/index.php Maszyna Turinga] w serwisie edukacyjnym [[I Liceum Ogólnokształcące im. Kazimierza Brodzińskiego w Tarnowie|I LO w Tarnowie]]