Машина Тьюринга: различия между версиями

м
м (Откат правок 62.231.181.231 (обс.) к версии 195.39.210.219)
'''Абстра́ктный автома́т''' (в [[w:теория алгоритмов|теории алгоритмов]]) — [[w:математика|математическая]] [[w:абстракция|абстракция]], [[w:модель|модель]] [[w:дискретное устройство|дискретного устройства]], имеющего один вход, один выход и в каждый момент времени находящегося в одном [[w:состояние|состоянии]] из множества возможных. На вход этому устройству поступают [[w:символ|символ]]ы одного [[w:язык|язык]]а, на выходе оно выдаёт символы (в общем случае) другого языка.
 
Формально абстрактный автомат определяется как пятеркапятёрка
 
<math>~A = (S, X , Y, \delta , \lambda)</math>
{{Акмар}}
 
С каждым определением мы всё больше вторгаемся в область чистой математики. Язык становится строже, появляются формальные определения, состоящие из математических символов. Если двигаться дальше, мы придём к теории алгоритмов и теории вычислимости. Путешествовать по страницам Википедии можно долго, но лучше запастись водой и едой, на случай забредания в пустыни аксиом и определений, или хотя бы надежныминадёжными ссылками на учебники по математике, например http://www.mccme.ru/free-books/, или статьи журнала "Потенциал" ;)
 
{{Стиль}}
Надеюсь, после этого объяснения вам стало немного яснее, что же такое машина Тьюринга?
 
Давайте вернемсявернёмся к истории этого термина.
 
Итак, Каккак мы уже упоминали, Алан Тьюринг поведал миру о своей машине в 1937 году в так называемом Тезисе Чёрча-Тьюринга. Про Алана Тьюринга — первого хакера и пионера информатики, как написано на мемориальной доске гостиницы, где он родился, поведает нам статья "Алан Тьюринг". Текст статьи полностью приводить здесь не будем, но она и сама по себе не очень подробная.
 
{{Рамка}}
13

правок