Машина на Тюринг: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Kerberizer (беседа | приноси) м {{цитат уеб/книга/периодика}} премахване на език-икона= / lang-icon= |
м Бот: Козметични промени |
||
Ред 1:
[[
'''Машина на Тюринг''' е абстрактно изчислително устройство, описано от английския математик [[Алън Тюринг]] през [[1936]] г.
Ред 14:
== Пример ==
Ще разгледаме машина, работеща с двубуквена азбука – буквите са '''0''' и '''1'''. Ще наречем нашата машина '''Double'''. Ето списъка от инструкциите
A 0:(0,s,R) 1:(0,B,R)
Ред 74:
Има ли алгоритъм, който да определя дали подадена на входа му компютърна програма решава задачата за удвояване на число, представено като поредица от единици?
Друга формулировка: Има ли машина на Тюринг, която да решава дали описана върху лентата
Горната задача е нерешима и в по-обща формулировка, известна като теорема на Райс, т.е. няма алгоритъм, който да установява еквивалентност на компютърни програми. Такъв тип нерешимост има важно практическо значение – ''не можем да създадем автоматизирани средства за проверка на коректността на компютърните програми''.
| |||