Машина Тьюринга – абстрактная вычислительная машина, была предложена Аланом Тьюрингом в 1936 году для демонстрации понятия алгоритма. Абстрактность заключается в том, что машина представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Машина Тьюринга состоит из неограниченной в обе стороны ленты, разделенной на ячейки, управляющего устройства, способного находиться в одном из множества состояний. Число возможных состояний управляющего устройства, конечно и точно задано. Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Алгоритм представляет собой совокупность правил функционирования машины, которые описываются как «если машина находится в таком-то состоянии и считывает с ленты такой-то символ, она делает то-то и переходит в такое-то состояние».
