Maszyna Turinga: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m substuję {{Definicja}} |
The Polish (dyskusja | edycje) drobne redakcyjne, drobne techniczne |
||
Linia 1:
[[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]]
'''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 w których zapisuje się dane. 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 ==
|