Описание машины Тьюринга

Лекция № 18

(лек. 2 час + прак. занят 2 час + лаб. 2 час. + самос. 2 час)

МАШИНЫ ТЬЮРИНГА

Описание машины Тьюринга

Абстрактная машина Тьюринга может рассматриваться как простейшая и одновременно все охватывающая модель любой реальной ЭВМ. Простота её устройства и принцип работы не оставляют даже места для возникновения вопроса "Может ли машина мыслить?"

Вопросы "Что такое алгоритм?", "Что такое алгоритмически разрешимые и неразрешимые проблемы?" стали особенно актуальными в XX веке в связи с развитием ЭВМ и естественной потребностью в аналитических возможностях. Теория алгоритмов была создана совместными (параллельными) усилиями, в основном американских, английских и советских математиков.

Осмысление понятия алгоритм потребовало и пересмотра многих философских воззрений на мышление как творческий процесс. Всегда ли, когда человек работает "головой", он думает? Если часть "головной" работы переложена на машину, то, следует ли считать что машина думает? Решение этих философских проблем принадлежит одному из крупнейших математиков XX века, основоположнику кибернетики А. Тьюрингу.

Машина Тьюринга имеет три алфавита:

1. Внешний алфавит с пустым символом A { }

2. Внутренний алфавит, или алфавит состояний Q={q₀, q₁, …, q_n}

Состояние q₀ - называется заключительным состоянием, q₁ - начальным состоянием, состояния q₀, q₁, …, q_n - рабочими состояниями.

3. Алфавит сдвигов S={-1, 0, +1}

Дата добавления: 2015-07-07