Работа - машина - тьюринг
Cтраница 1
Работа машины Тьюринга протекает следующим образом. Дальнейший процесс протекает уже автоматически и однозначным образом определяется функциональной схемой машины. [1]
Работа машины Тьюринга складывается из следующих один за другим тактов. Очередное значениеy ( t l) записывается головкой в ячейку. [2]
Работа машины Тьюринга зависит от характера исходной записи ленты. [3]
Прослеживая работу машины Тьюринга, мы узнаем, что она применима к данному слову, но если она неприменима, то такое прослеживание нам ничего не докажет, так как в любой момент можно надеяться на то, что она скоро остановится. Итак, неприменимость не может быть выяснена прямым способом; в ней можно убедиться только косвенными рассуждениями. Например, если в имеющейся программе нет клетки останова, то данная машина Тьюринга не применима ни к одному слову. [4]
Рассмотрим работу машины Тьюринга на задаче прибавления единицы к числу на ленте. Входное слово состоит из цифр этого числа, записанных в последовательные ячейки ленты. В начальный момент автомат находится против самой правой цифры числа. Машина должна прибавить единицу к последней цифре, а если это была цифра 9, то заменить ее на 0 и аналогично поступить с предыдущей цифрой. [5]
Существенная особенность работы машины Тьюринга состоит в том, что на каждом такте преобразование информации происходит только в одной ячейке; остальные же ячейки в это время дожидаются посещения головки. Конечно, бывают случаи, когда такое ожидание оправдано природой решаемой задачи. Однако легко представить себе и иные ситуации, когда такой зависимости нет, и, следовательно, единственная причина, по которой преобразования в ячейках 3 и а не осуществляются одновременно ( параллельно), заключается лишь в том, что машина Тьюринга не в состоянии этого делать. [6]
 |
Алгоритм работы машины Тьюринга по переработке слова 1 1 100 в слово 1 1 1 10. [7] |
В результате работы машины Тьюринга за четыре шага это слово превращается в НПО. По окончании работы машины головка стоит над крайней правой единицей. [8]
Из приведенного описания ясно, что работа машины Тьюринга вполне определяется той логической функцией, которую реализует логический блок. [9]
Пусть Т ( 1) - время работы одноленточной машины Тьюринга, которая вычисляет Т ( 1) на ogT ( l) ячейках ленты. [10]
Теперь мы рассмотрим классы сложности, определенные через время работы одноленточ-ных машин Тьюринга. [11]
Всякая вычислительная процедура, к-рая может быть сведена к работе подходящей машины Тьюринга, является эффективной в интуитивном смысле. Этот тезис нельзя доказать, так как он объединяет два понятия - строгое математич. [12]
Поскольку в этой книге мы заинтересованы лишь в наблюдении за работой машины Тьюринга и за результатами этой работы, то для нас совершенно безразлично, интерпретируем ли мы функциональные схемы как характеристики логических блоков специализированных машин Тью-рийга, или как тьюринговы программы, доступные одному и тому же вычислителю. [13]
Изложенная идея синтаксического анализа методом Наура имеет некоторое сходство с принципом работы машины Тьюринга с тремя лентами. [14]
С другой стороны, критики искусственного интеллекта считают, что роль вычислений ( выполняемых подобно работе машины Тьюринга) в процессе мышления переоценивается ( ср. Однако нет оснований предполагать, что мозг содержит одни лишь тьюрин-говские ( алгоритмические) мыслительные блоки. Наши р-адиче-ские математические модели показывают, что многие черты когнитивного поведения можно моделировать с помощью динамических сетей, выполненных нетьюринговскими преобразованиями 1), см. гл. [15]
Страницы: 1 2 3