Машина - тьюринг
Cтраница 1
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и считывающей и записывающей головки. Последовательное выполнение этих трех операций называется тактом. [1]
Машина Тьюринга М0, описанная выше, обладает емкостной сложностью S2 () и допускает некоторый язык L. [2]
Машина Тьюринга должна уметь читать и писать. Читает она бумажную ленту, разделенную на клетки, и пишет на этой же ленте. С одной стороны лента ограничена, с другой - простирается до бесконечности. Машина знает эти цифры: умеет их читать и писать. [3]
Машина Тьюринга задана внешним алфавитом А - О, , , внутренним алфавитом Q qo, q, qz, 7з где 0 - пустой символ, а 7з - заключительное состояние. [4]
Машина Тьюринга с входной лентой называется линейно-ограниченной, если существует такое число с, что в процессе до-пускания цепочки и машина не может использовать более чем с - м рабочих ячеек. [5]
Машина Тьюринга состоит из устройства управления, которое с помощью головки связано с лентой ввода / вывода. Головка указывает на какую-то одну ячейку ленты и может читать содержимое ячейки, записывать и перемещаться вправо или влево. В начале работы исходные данные всегда заполняют левую часть ленты, а головка читает самую левую ячейку ленты. [6]
Машина Тьюринга называется стандартной, если она при сдвиге ленты может предварительно изменять состояние воспринимаемой ячейки. [7]
 |
Алгоритм работы машины Тьюринга по переработке слова bcadc в слово bcdcc. [8] |
Машины Тьюринга представляют собой универсальных исполнителей, с использованием которых можно имитировать все алгоритмические процессы, описываемые математиками. Было доказано, что класс функций, вычислимых на этих машинах, точно совпадает с классом всех частично рекурсивных функций. [9]
Машина Тьюринга обладает столь колоссальными возможностями именно потому, что она опирается на такой теоретический фундамент. [10]
Машина Тьюринга, являясь очень простой моделью, наиболее пригодна для получения нижних оценок сложности алгоритма, но написание программы для машины Тьюринга достаточно сложно, и, кроме того, такая программа не наглядна. Такая оценка приемлема в том случае, когда числи символов, необходимых для записи констант и значений переменных программы, ограничено некоторой величиной, не зависящей от длины входа. [11]
Машина Тьюринга представляет собой автомат, который может двигаться вдоль бесконечной ленты. Лента разделена на ячейки. [12]
Машины Тьюринга не только соответствуют некоторым алгоритмам специального вида, но и сами являются ими. Действительно, читатель уже понял, что машины Тьюринга - это воображаемые машины, существующие не физически, а идеально, в наших мыслях, а точнее - в виде некоторых текстов на естественном языке. Сконструировать машину Тьюринга - значит составить ее описание, а не изготовить техническое устройство. Работа машины Тьюринга заключается в том, что человек выполняет определенные действия, руководствуясь описанием машины Тьюринга и ее функциональной таблицей, имея заданное начальное ( подлежащее преобразованию) слово и получая на очередном шаге промежуточный результат. [13]
Машина Тьюринга работает следующим образом. [14]
Машина Тьюринга содержит две памяти: неограниченную ленту и управляющий механизм с конечным числом состояний. Набор операций, которые машина может совершать над лентой, очень мал: чтение, запись и просмотр. Операция чтения не меняет данных, но обеспечивает условные переходы управления в зависимости от данных, находящихся под читающей головкой. Как нам всем известно, эта модель содержит существенные свойства любого компьютера в смысле того, что компьютеры вообще могут делать, хотя разные компьютеры с разными регистрами памяти и разными наборами операций способны выполнять одни и те же вычисления, расходуя разные объемы памяти и требуя разного времени на их выполнение. [15]
Страницы: 1 2 3 4