Машина Тьюринга (1) - Современная математизированная формальная логика представляет собой обширную научную область, которая находит широкое применение как внутри математики (исследование оснований математики), так и вне её (синтез и анализ автоматических устройств, теоретическая кибернетика, в частности, искусственный интеллект).
- Машина Тьюринга – это абстрактное вычислительное устройство, которое было предложено в 1936 г. английским математиком Аланом Тьюрингом (Alan Mathison Turing) в качестве математической модели для описания алгоритмов.
- Первоначально концепция машины Тьюринга развивалась с целью ответа на вопрос: можно ли для любого математического утверждения указать конечную последовательность инструкций, которые могли бы выполняться механически одна за другой любым человеком или вычислительным устройством, и в итоге выяснить, истинно это утверждение или ложно.
Машина Тьюринга (2) - Машина Тьюринга является дискретным вычислительным устройством, изменяющим свои характеристики в определённые моменты времени.
- Машина Тьюринга имеет ленту с ячейками для хранения данных и обрабатывающий элемент, внешний по отношению к ленте, но обеспечивающий подачу команд, модифицирующих ячейки ленты.
- В 1936 г. А. Чёрчем была высказана гипотеза, что любой процесс, который естественным образом мог бы быть назван процедурой, реализуем машиной Тьюринга. Впоследствии эту гипотезу стали называть тезисом Чёрча-Тьюринга. В этом смысле машина Тьюринга считается эквивалентной любому вычислительному устройству.
- В том же 1936 г. польский математик А. Тарский доказал, что поставленная проблема в общем случае неразрешима. Однако применение машины Тьюринга вышло далеко за пределы первоначальной постановки. По существу именно работы Тьюринга положили начало математической теории вычислений.
- Машина Тьюринга сыграла и продолжает играть важную роль в теории информатики, а вычислимость при помощи машины Тьюринга стала признанным определением процедуры.
Do'stlaringiz bilan baham: |
