Возможности вычислительных машин и человеческий разум



         

Глава 2. Откуда возникает мощь вычислительной машины - стр. 23


Таким образом, в очень медленном темпе, шаг за шагом, и чрезвычайно точно имитируется работа нашей исходной суммирующей машины, т. е. машины, заданной новой машине через описание на ленте последней. Следовательно, машина олицетворяет правила, указывающие, каким образом интерпретируются цепочки иксов, единиц и нулей, предлагаемые ей нами.

Машину, которая перемещает ленту вперед и назад, считывая или изменяя метки на каждом такте в одной ячейке ленты и переходя из одного состояния в другое и так далее, теперь называют машиной Тьюринга. Описание такой машины является полным при условии, что для каждого ее допустимого состояния и для каждого символа, который может оказаться под ее считывающей головкой, это описание указывает, какой символ следует записать, в какое состояние должен произойти переход и в каком направлении машина должна передвинуть ленту. Можно в качестве особого условия оговорить, что всякая машина такого типа начинает свою работу из первого состояния (назовем его состоянием 1), причем лента расположена таким образом, что крайний правый записанный на ней символ располагается под головкой считывания (записи). Мы пользовались здесь языком, алфавит которого насчитывает три символа, с помощью их мы описывали нашу суммирующую машину. Если бы мы были щедрее, т. е. воспользовались алфавитом большего объема, наша машина могла бы быть проще - она имела бы меньше состояний. Правила же оказались бы более сложными. Существует, таким образом, множество возможных реализаций нашей суммирующей машины - по меньшей мере, по одной на каждый существенно новый алфавит, который мы могли бы выбрать. Минимальный объем алфавита, который можно использовать, равен двум - суммирующая машина типа нашей должна иметь большое число состояний, чтобы работать со столь ограниченным алфавитом. Минимальное число состояний, которое подобная суммирующая машина должна была бы иметь, равно двум, но такая машина должна оперировать большим алфавитом.

Существует важное различие между двумя рассматриваемыми машинами.


Содержание  Назад  Вперед