Тьюринга машина это:

Тьюринга машина
        название, закрепившееся за абстрактными (воображаемыми) «вычислительными машинами» некоторого точно охарактеризованного типа, дающими пригодное для целей математического рассмотрения уточнение общего интуитивного представления об Алгоритме. Концепция такого рода машины сложилась в середине 30-х гг. 20 в. у А. М. Тьюринга в результате произведённого им анализа действий человека, выполняющего в соответствии с заранее разработанным планом те или иные вычисления, то есть последовательные преобразования знаковых комплексов.
         Т. м. удобно представлять в виде некоторого автоматически действующего устройства, способного находиться в конечном числе внутренних состояний и снабженного бесконечной внешней памятью — лентой. Среди состояний имеются два выделенных — начальное и заключительное. Лента разделена на клетки (ячейки) и не ограничена влево и вправо. В каждой клетке ленты может быть записан любой из символов, входящих в некоторый заранее заданный перечень (ради единообразия считают, что в пустой клетке записана «пустая буква»). В каждый момент времени Т. м. находится в одном из своих состояний и, рассматривая (посредством специального устройства) одну из клеток своей ленты, воспринимает записанный в ней символ. Если в текущий момент времени Т. м. находится в не заключительном состоянии, то в следующий за ним момент: 1) она переходит в новое состояние, быть может совпадающее со старым, или заключительное; 2) в рассматриваемой клетке старый символ заменяется новым, быть может пустым или совпадающим со старым; 3) лента машины сдвигается на одну клетку влево или вправо либо остаётся на месте. Этот шаг Т. м. вполне определяется её текущим состоянием и текущим воспринимаемым символом. Таблица, содержащая полное перечисление возможных шагов данной Т. м., называется программой этой машины.
         Текущее полное описание Т. м. даётся её конфигурацией, которая состоит из указания для данного момента следующей информации: 1) конкретного заполнения клеток ленты символами, 2) клетки, находящейся в поле зрения машины, 3) состояния, в котором машина находится.
         Если у данной Т. м. взять в качестве исходной какую-либо конфигурацию с не заключительным состоянием, то работа этой машины будет заключаться в последовательном, шаг за шагом, преобразовании исходной конфигурации в соответствии с программой машины до тех пор, пока не будет достигнута конфигурация с заключительным состоянием. Эта последняя, если она существует, и считается результатом работы данной Т. м. над исходной конфигурацией.
         Имеются серьёзные основания считать, что понятие Т. м. доставляет адекватное уточнение общего представления об алгоритме, то есть что всякий алгоритм может быть промоделирован подходящей Т. м. Соответствующее соглашение известно в алгоритмов теории (См. Алгоритмов теория) под названием тезиса Тьюринга. Теория Т. м. даёт удобный рабочий аппарат для многих исследований, требующих точного понятия алгоритма. В частности, ввиду естественности совершаемых ими шагов, Т. м. стали объектом пристального внимания в теории сложности алгоритмических вычислений. В ходе развития теории Т. м. рассматривались различные их обобщения: например, Т. м. с более общим типом лент, с несколькими лентами, а также недетерминированные Т. м.
         Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; Мендельсон Э., Введение в математическую логику, пер. с англ., М., 1971.
         Н. М. Нагорный.

Большая советская энциклопедия. — М.: Советская энциклопедия. 1969—1978.

Смотреть что такое "Тьюринга машина" в других словарях:

  • Тьюринга машина — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… …   Википедия

  • ТЬЮРИНГА, МАШИНА — Абстрактный автомат (то есть компьютер или другой точный, определенный механизм), теоретически охарактеризованный британским математиком Аланом М. Тьюрингом в 1930 х гг. В основном, машина Тьюринга состоит из ленты и считывающей головки. Лента… …   Толковый словарь по психологии

  • ТЬЮРИНГА МАШИНА — название, закрепившееся за вычислительными машинами абстрактными нек рого точно охарактеризованного типа. Концепция такого рода машины возникла в середине 30 х гг. 20 в. у А. М. Тьюринга [1] в результате произведенного им анализа действий… …   Математическая энциклопедия

  • ТЬЮРИНГА МАШИНА — предложенная А. Тьюрингом в 1937 абстрактная модель вычислит. машины. Послужила теоретич. основой создания совр. ЭВМ …   Естествознание. Энциклопедический словарь

  • Машина Тьюринга для умножения чисел — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… …   Википедия

  • Машина тьюринга — (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча Тьюринга, способна …   Википедия

  • Машина Тьюринга — математическое построение, предназначенное для уточнения понятия алгоритма. Машина Тьюринга состоит: из неограниченной в обе стороны ленты, разделенной на ячейки; из головка чтения/записи, которая может перемещаться вдоль ленты. Программа для… …   Финансовый словарь

  • Машина Тьюринга — Художественное представление машины Тьюринга Машина Тьюринга (МТ)  абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма …   Википедия

  • МАШИНА — (в математике) абстрактное устройство, осуществляющее переработку информации. Употребительны также термины абстрактная машина , автомат . Абстрактные М. являются частным случаем управляющих систем. Возникновение их связано с анализом понятия… …   Математическая энциклопедия

  • Машина Поста — (МП) абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм». Содержание 1 Принцип… …   Википедия

Книги

  • Тест Тьюринга, Джесси Рассел. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. High Quality Content by WIKIPEDIA articles! Тест Тьюринга — эмпирический тест, идея которого была… Подробнее  Купить за 1125 руб
  • Машина Тьюринга, Джесси Рассел. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. High Quality Content by WIKIPEDIA articles! Маши?на Тью?ринга (МТ) — абстрактный исполнитель… Подробнее  Купить за 998 руб
  • Может ли машина мыслить, . Настоящая книга, содержащая работы Алана Тьюринга и Джона фон Неймана, стоявших у истоков создания первых"мыслящих машин"ЭВМ, относится к классике философско-кибернетического направления… Подробнее  Купить за 328 руб
Другие книги по запросу «Тьюринга машина» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»