машина Тьюринга
Машина Тьюринга — это математическая модель вычислений , определяющая абстрактную машину [1] , которая манипулирует символами на полосе ленты в соответствии с таблицей правил. [2] Несмотря на простоту модели, для любого компьютерного алгоритма можно построить машину Тьюринга, способную реализовать логику этого алгоритма. [3]
Машина работает на бесконечной [4] ленте памяти, разделенной на дискретные «ячейки». [5] Машина позиционирует свою «голову» над ячейкой и «считывает» или «сканирует» [6] символ в ней. Затем, основываясь на символе и собственном текущем состоянии машины в «конечной таблице» [7] заданных пользователем инструкций, машина сначала записывает символ (например, цифру или букву из конечного алфавита) в ячейку ( некоторые модели допускают стирание символов или запрет на запись), [8] , затем перемещают ленту на одну ячейку влево или вправо (некоторые модели не допускают движения, некоторые модели перемещают головку), [9]затем, основываясь на наблюдаемом символе и собственном состоянии машины в таблице, либо переходит к другой инструкции, либо останавливает вычисления. [10]
Машина Тьюринга была изобретена в 1936 году Аланом Тьюрингом [11] [12] , который назвал ее «а-машиной» (автомат). [13] Используя эту модель, Тьюринг смог ответить отрицательно на два вопроса:
Таким образом, предоставив математическое описание очень простого устройства, способного к произвольным вычислениям, он смог доказать свойства вычислений вообще — и, в частности, невычислимость Entscheidungsproblem («проблема принятия решения») . [16]
Машины Тьюринга доказали существование фундаментальных ограничений мощности механических вычислений. [17] Хотя они могут выражать произвольные вычисления, их минималистский дизайн делает их непригодными для вычислений на практике: компьютеры реального мира основаны на других конструкциях, которые, в отличие от машин Тьюринга, используют оперативную память .
Полнота по Тьюрингу — это способность системы инструкций имитировать машину Тьюринга. Язык программирования, полный по Тьюрингу, теоретически способен выразить все задачи, решаемые компьютерами; почти все языки программирования являются полными по Тьюрингу, если игнорировать ограничения конечной памяти.
