Итак, инструкция вообще может не быть соот
ветствием, но если она может быть рассмотрена как соответствие, то совер
шенно не обязательным является то, чтобы это с о ответст
вие было функциональным. Соответствие является функциональ ны
м если элеме н ту из области определения функции соответ
ствует только один элемент из области знач е ний. «Функц
иональное соответствие» является своего рода промежуточным между ст
и хийным и деликатным.
Приведу примеры. Допустим, я «стреляю из пистолета» с др
узьями на стадионе , если хотите, «нажимаю на спусковой крючок». Э
та инструкция из тех, которые имеют зн а чение: первое, чт
о приходит в голову то, что значением инструкции будет «выстрел». Мо
ж но в самом деле указывать на зависимость, даже функцио
нальную, между моделями пистолета и со б ственно «выстр
елом» по дальности и другим параметрам. Но, допустим, я стреляю из пистоле
та в районе стадиона, где к старту приготовилась группа спортсменов. Я вы
стрелю, а они побегут. Старт группы спортсменов будет таким же зн
ачением инс т рукции «стрелять из пистолета» как и «выс
трел». И дело здесь как раз не в том, что спор т смены реаги
руют на «выстрел», а не на стрельбу из пистолета, что «выстрел» предшес
т вует ста р ту. На практике мы сталкива
емся с фальш-стартами. В конце концов пистолет может дать осечку, но это вы
зовет старт. Таким образом то, что спортсмены стартуют я в
ляется точно т а ким же значением инструкции «с
трелять из пистолета» как и «выстрел». Выстрелив из пистолета может разд
аться выстрел и последовать старт, а может послед о вать
только одно значение, а может не последовать ни одного. Данное со
ответствие не я в ляется функци о нальны
м.
Допустим, я постоянно покупаю вино в одном магазине. Для того, что
бы получить бутылку вина я расплачиваюсь. Речь идет о соответствии между
суммой денег и бутылкой вина определенной марки. Это соответствие также
функциональным не является. Во-пер в ых, это вино постоян
но дорожает как в зависимости от инфляции так и по неизвес т
ным мне пр и чинам, так что когда я составляю дома
шний бюджет одному и тому же вину соответствует несколько сумм денег. Ка
к-то раз под Новый г од хозяин магазина сделал мне как пос
тоянному покупателю подарок Ц он подарил мне бутылку. Я никогда с точн
о стью не знаю на какую сумму мне рассчитывать, чтобы куп
ить вино, сколько мне нужно выложить пр о давцу, чтобы пол
учить бутылку.
В конце концов я выкладываю сумму денег в магазине за какой-либо
товар, пре д полагая получить не только товар, но и сдачу.
Моей сумме денег соответствует два знач е ния -- «товар» и
«сдача». Но таким образом это действие не является функцией. Однако если
спросить человека в здравом уме является ли это действие чем-то «единым»
, «о д ним», является ли для него естественным заплатить с
умму денег за товар и получить т о вар и
сдачу или он считает, что он совершает два разных действия, то, я полагаю, ч
еловек в здр а вом уме согласится, что это одно действие. Э
то действие я называю инструкцией и прот и вопоставляю ф
ункции.
Допустим, я играю на рулетке. Предполагая выиграть, я делаю ставк
у. «Делать ставку» это инструкция, которая очевидно может иметь два знач
ения Ц выигрыш и прои г рыш. Любой здесь заявит: «да в дан
ном случае мы не имеем дело с функцией».

45 . Однако все эти соответствия могут быть форма
лизованы, для них могут быть заданы алгоритмы.
Допустим
( z
, y ) = 2 x

при z =2 x , если
x - четное,
y =2 x ,
если x -нечетное.

Скажут, вы в данном случае задали д
ве функции, для четных и нечетных чисел. Я этого не делал. Я просто записал
одну инструкцию. Надеюсь, эта инструкция совершенно интуитивно
ясна человеку в здравом уме, однако термина для нее в математике не сущ
е ствовало.

46 . Фундаментальной идеей , с кот
орой вы должны ознакомиться , является не идея функции, к
ак функционального соотвествия, а машин а Тюри
нга-Поста. Этот термин де й ствительно имеет фун
даментальное значение для математики, программирования, а, как я убежден
, и общенаучный смысл. Я изложу его содержание.
Исходным материалом для нас будет с
лужить такое соответствие как лент а , разд
е ленн ая на равные участки, называемые ячейка
ми. Лента будет считаться конечной длины в ка ж дый момент вр
емени, неограниченно продолжаемой в обе стороны и направленной, так что
у каждой ячейки есть соседняя справа и соседняя слева. Каждая ячейка лен
ты м о жет находиться в различных состояниях и эти состояни
я сравнимы, так что можно одн о значно решить, находятся ли дв
е произвольные ячейки ленты в одинаковых состояниях или в разных. Одно и
з возможных состояний ячеек называется исходным. Ячейки, нах о
дящиеся в этом состоянии называются пустыми. Остальные состояния
обозначаются бу к вами , з
а нимающими соответствующие ячейки. Произвольная конечная
совокупность букв называется алфавитом . Если говоря
т, что имеют алфавит состоящий из букв А,В то это значит, что рассматривает
ся лента, ячейки которой могут находиться в состояниях, усло в
но обозначаемых символами А,В. Последовательность ячеек, занятых
некоторыми букв а ми, называется словом .
Словом в данном алфавите называется каждое слово, все буквы которого при
на д лежат этому алфавиту. Если алфавит состоит из букв А,В,С,
то слова А, ВАА, СА, ВВ, ССАВВ будут словами в этом алфавите. Длиной слова наз
ывается число вход я щих в него символов. Так длинами написа
нных выше слов являются числа 1, 3, 2, 2, 5.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62