Машина Тьюринга — это абстрактный исполнитель (абстрактная вычислительная машина), предложенная Аланом Тьюрингом в 1936 году для определения понятия алгоритма. 2 Она состоит из трёх элементов: бесконечной ленты с ячейками, автомата или головки для чтения и записи, и программы. 4

Линейный ограниченный автомат — это недетерминированная одноленточная машина Тьюринга, которая никогда не покидает те ячейки, на которых размещён её ввод. 5 Отличается от машины Тьюринга тем, что, хотя изначально лента имеет неограниченную длину, головка чтения/записи может получить доступ только к конечной непрерывной части ленты, длина которой является линейной функцией длины начального ввода. 1