Машина на Тюринг: Разлика между версии
Изтрито е съдържание Добавено е съдържание
м r2.7.1) (Робот Добавяне: eu:Turingen makina |
м форматиране: 5x интервали, й→ѝ (ползвайки Advisor.js) |
||
Ред 12:
== Пример ==
Ще разгледаме машина, работеща с двубуквена азбука — буквите са '''0''' и '''1'''. Ще наречем нашата машина '''Double'''. Ето списъка от инструкциите
A 0:(0,s,R) 1:(0,B,R)
B 0:(1,C,L) 1:(1,B,R)
C 0:(1,A,L) 1:(1,C,L)
Имената на инструкциите са големите латински букви '''A''', '''B''' и '''C'''. С малка буква '''s''' сме означили специалната инструкция за спиране на изчислението.
Всяка инструкция съдържа 2 указания — какво да прави при прочетена 0 или 1. Например инструкцията '''B''' при прочетена 0 трябва да изпълни указанието (1,C,L), чието тълкувание е: запиши върху лентата 1, следващата активна инструкция ще е C, премести главата наляво.
Предназначението на тази проста машина е да удвоява поредица от единици, при следните условия: в началото лентата съдържа поредица от няколко единици, а всички останали клетки са празни (т.е. заети от символа 0) и главата се намира над най-дясната единица и началната активна инструкция е '''A'''. Започвайки изчислението, машината в крайна сметка ще спре, като броят на единиците в поредицата ще е два пъти по-голям от началния им брой.
Ред 27:
ст. инс. лента
-- - ----------------
1 A 011'''1'''0000
2 B 0110'''0'''000
Ред 56:
== Изчислимост и алгоритми ==
През 30-те години на XX век били предложени няколко математически определения на понятието ефективен метод (алгоритъм, формална процедура, изчисляващо устройство, компютър). Било също доказано, че всички такива определения са еквивалентни, т.е. класа задачи, които можем да решим с някоя от предложените схеми (примерно с машини на Тюринг) точно съвпада с класа задачи, решими с всяка друга разумна схема за правене на изчисления (примерно най-мощните съвременни компютри, с допълнителна възможност да им добавяме памет по време на изчислението). Тази еквивалентност, приемана като природен закон за всички възможни схеми за изчисляване се нарича [[тезис на Чърч]] по името на американският логик Алонсо Чърч, който я забелязва най-рано.
Тезисът на Чърч позволява да се дефинира (определи) понятието алгоритъм така:
Ред 82:
Нерешимите задачи имат пряка връзка с основите на математиката и математическата логика. Известната [[теорема на Гьодел за непълнота]], изключително важен резултат за математиката и цялата наука и философия, доказана още през 1932 г. конструира специално неразрешимо твърдение за всяка достатъчно богата формална математическа теория. Това Гьоделево твърдение, което нито може да се докаже, нито да се опровергае със формални математически методи по същество е еквивалентно на алгоритмично нерешима задача.
== Вижте също ==
* [[Алгоритъм]]
[[Категория:Теоретична информатика]]
[[als:Turing-Maschine]]
| |||