Cтраница 3
Если считывающая головка приходит на пустой квадрат, то она должна или остановиться здесь на все время, или же передвинуться вправо либо влево. Так как имеется лишь одно состояние, то ее поведение не зависит от предшествовавшего вычисления. В первом случае считывающая головка никогда не отойдет дальше, чем на один квадрат, от описательного числа, и вся лента, кроме конечного отрезка, будет постоянно пуста. Если же головка передвигается влево с некоторого пустого квадрата, то или левая бесконечная часть пустой ленты не участвует в вычислении и поэтому не требует рассмотрения, или, если она участвует в вычислении, считывающая головка с этого времени беспрерывно движется влево, записывая во всех квадратах, ранее пустых, один и тот же символ. Аналогичное положение возникает при движении головки вправо от первоначально пустого квадрата. Поэтому двусторонне бесконечная лента ничуть не лучше односторонней, и можно из соображений симметрии предположить, что лента односторонне бесконечна вправо от описательного числа. [31]
На этой ленте записана входная цепочка. Терминальные символы этой цепочки закодированы символами словаря лент. Головка на входной ленте стоит в начальный момент на крайнем левом непустом квадрате. Эта головка может сдвигаться только вправо, воспринимая одиночный пустой квадрат как конец символа, а пару пустых квадратов как конец цепочки. [32]
Можно показать, что в этом случае символы в первоначально пустой части становятся, за исключением конечного их числа, одинаковыми. В самом деле, либо головка передвигается вправо из первого пустого квадрата во второй пустой квадрат по меньшей мере R 1 раз, либо нет. В последнем случае спустя конечное время считывающая головка остается в бывшем первом пустом квадрате, и вся лента, кроме конечной части, остается пустой. Если же головка уходит вправо К 1 раз, то она не вернется в первый квадрат, первоначально пустой, ибо R есть число отражений для пустой ленты. Во втором первоначально пустом квадрате в конце, концов будет записан тот же самый постоянный символ, потому что ко второму квадрату применимо такое же рассуждение, как и к первому. Во всех случаях машина работает на той же самой ленте ( бесконечном ряде пустых квадратов) и приходит одно и то же число раз справа ( R) и соответственно ( R 1) слева. Тем самым все возможные случаи исчерпаны и доказательство завершено. [33]
На этой ленте записана входная цепочка. Терминальные символы этой цепочки закодированы символами словаря лент. Головка на входной ленте стоит в начальный момент на крайнем левом непустом квадрате. Эта головка может сдвигаться только вправо, воспринимая одиночный пустой квадрат как конец символа, а пару пустых квадратов как конец цепочки. [34]
Теперь расчленим управляющее устройство G-машины. Оно состоит из управляющего устройства ( У-машины ( U означает универсальность) и двух лент. Другими словами, добавив две ленты для работы с грамматикой и изменив управляющее устройство, мы можем создать ( / - машину, которая будет выполнять распознавание для любой контекстно-свободной грамматики в нормальной форме. Одна из дополнительных лент - входная; на ней записана грамматика в виде трех массивов, разделенных одиночными пустыми квадратами. [35]
Если считывающая головка приходит на пустой квадрат, то она должна или остановиться здесь на все время, или же передвинуться вправо либо влево. Так как имеется лишь одно состояние, то ее поведение не зависит от предшествовавшего вычисления. В первом случае считывающая головка никогда не отойдет дальше, чем на один квадрат, от описательного числа, и вся лента, кроме конечного отрезка, будет постоянно пуста. Если же головка передвигается влево с некоторого пустого квадрата, то или левая бесконечная часть пустой ленты не участвует в вычислении и поэтому не требует рассмотрения, или, если она участвует в вычислении, считывающая головка с этого времени беспрерывно движется влево, записывая во всех квадратах, ранее пустых, один и тот же символ. Аналогичное положение возникает при движении головки вправо от первоначально пустого квадрата. Поэтому двусторонне бесконечная лента ничуть не лучше односторонней, и можно из соображений симметрии предположить, что лента односторонне бесконечна вправо от описательного числа. [36]
Можно показать, что в этом случае символы в первоначально пустой части становятся, за исключением конечного их числа, одинаковыми. В самом деле, либо головка передвигается вправо из первого пустого квадрата во второй пустой квадрат по меньшей мере R 1 раз, либо нет. В последнем случае спустя конечное время считывающая головка остается в бывшем первом пустом квадрате, и вся лента, кроме конечной части, остается пустой. Если же головка уходит вправо К 1 раз, то она не вернется в первый квадрат, первоначально пустой, ибо R есть число отражений для пустой ленты. Во втором первоначально пустом квадрате в конце, концов будет записан тот же самый постоянный символ, потому что ко второму квадрату применимо такое же рассуждение, как и к первому. Во всех случаях машина работает на той же самой ленте ( бесконечном ряде пустых квадратов) и приходит одно и то же число раз справа ( R) и соответственно ( R 1) слева. Тем самым все возможные случаи исчерпаны и доказательство завершено. [37]
Такое перемещение можно описать строго формально в терминах операторов, рассматривая пустой квадрат как некоторый объект, который может быть передвинут в любом из четырех направлений. Это дает четыре оператора - вверх, вниз, влево, вправо - которые могут быть применены к некоторому состоянию лотка, порождая новое состояние. На рис. 3.2 показаны результаты применения этих операторов к начальному состоянию такой игры. Определенные операторы могут оказаться неприменимыми в некоторых состояниях. В нашей игре оператор неприменим, если пустой квадрат находится на краю лотка и рассматриваемый оператор должен был бы столкнуть его с лотка. [38]
Теперь расчленим управляющее устройство G-машины. Оно состоит из управляющего устройства ( У-машины ( U означает универсальность) и двух лент. Другими словами, добавив две ленты для работы с грамматикой и изменив управляющее устройство, мы можем создать ( / - машину, которая будет выполнять распознавание для любой контекстно-свободной грамматики в нормальной форме. Одна из дополнительных лент - входная; на ней записана грамматика в виде трех массивов, разделенных одиночными пустыми квадратами. Квадрат, отстоящий на ( / - ) q k квадратов от ближайшего левого пустого квадрата, содержит 1, тогда и только тогда, когда Ah - ai есть терминальное правило, и 0 в противном случае. Третий массив занят двойными правилами грамматики и занимает q3 квадратов. Здесь квадрат, отстоящий на ( k - 1) 72 ( k - ) q k2 квадратов от ближайшего левого пустого квадрата, содержит 1, если Л, ь - A k [ Ak2 - двойное правило грамматики, и 0 в противном случае. [39]
Можно показать, что в этом случае символы в первоначально пустой части становятся, за исключением конечного их числа, одинаковыми. В самом деле, либо головка передвигается вправо из первого пустого квадрата во второй пустой квадрат по меньшей мере R 1 раз, либо нет. В последнем случае спустя конечное время считывающая головка остается в бывшем первом пустом квадрате, и вся лента, кроме конечной части, остается пустой. Если же головка уходит вправо К 1 раз, то она не вернется в первый квадрат, первоначально пустой, ибо R есть число отражений для пустой ленты. Во втором первоначально пустом квадрате в конце, концов будет записан тот же самый постоянный символ, потому что ко второму квадрату применимо такое же рассуждение, как и к первому. Во всех случаях машина работает на той же самой ленте ( бесконечном ряде пустых квадратов) и приходит одно и то же число раз справа ( R) и соответственно ( R 1) слева. Тем самым все возможные случаи исчерпаны и доказательство завершено. [40]
Пусть переменная Т с соответствующими индексами обозначает квадраты досги. Значение iU B означает, что игрок занимает этот квадрат. В случае значения 01 В квадрат занимает вычислительная машина. Если же значение равно ОО В, то это означав. Игроку предоставляется право сделать первый ход. Игрок указывает свои ходы путем ввода двух целых чисел, определяющих строку и колонку ( 1, 2 или 3), в которых он намеревается сделать свою отметку. Программа должна делать выбор из числа пустых квадратов и выдавать на печать доску ( для игры в крестики и нолики) с использованием обозначения X для игрока и 0 для вычислительной машины. [41]
Теперь расчленим управляющее устройство G-машины. Оно состоит из управляющего устройства ( У-машины ( U означает универсальность) и двух лент. Другими словами, добавив две ленты для работы с грамматикой и изменив управляющее устройство, мы можем создать ( / - машину, которая будет выполнять распознавание для любой контекстно-свободной грамматики в нормальной форме. Одна из дополнительных лент - входная; на ней записана грамматика в виде трех массивов, разделенных одиночными пустыми квадратами. Квадрат, отстоящий на ( / - ) q k квадратов от ближайшего левого пустого квадрата, содержит 1, тогда и только тогда, когда Ah - ai есть терминальное правило, и 0 в противном случае. Третий массив занят двойными правилами грамматики и занимает q3 квадратов. Здесь квадрат, отстоящий на ( k - 1) 72 ( k - ) q k2 квадратов от ближайшего левого пустого квадрата, содержит 1, если Л, ь - A k [ Ak2 - двойное правило грамматики, и 0 в противном случае. [42]