|
[125] 2. Более строго операцию подстановки можно задать следующим образом. По n‑местным функциям q1..., gm и m‑местной функции h строится n‑местная функция f такая, что для любых x1, x2,..., Хn(x1, x2,..., Хn) = h(x1, ... Хn),... gm(x1,... Хn)). [126] 3. Обращаем внимание на то, что в определениях операторов I–III знак равенства (=) следует понимать как знак так называемого условного равенства (?). Соединение двух выражений, в которых могут фигурировать знаки частичных функций, знаком условного равенства,‑понимается как следующее утверждение: для любого из двух выражений из того, что определено одно из них, вытекает, что определено и другое и их значения совпадают. [127] 4. Отметим в этой связи, что приведенное там же определение функции ? подпадает под схему II для случая, когда отсутствуют параметры рекурсии (см. с. 137 – 138). Роль f играет функция ?, в качестве r берется 0, а в качестве h – проектирующая функция I12. [128] 5. См. А. И. Мальцев. Алгоритмы и рекурсивные функции. М., 1965, с. 12 и далее. [129] 6. Имеется в виду статья: L. Kalmar. An Argument against the Plausibiolitu of Church's Thesis. «Constructivity in Mathematics. Proceedings of the Colloquium held at Amsterdam». Amsteerdam, 1959, p. 72–73. [130] 7. Имеется в виду работа : А. Church. An Unsolvable Problem of Elementary Number Theory. «American Journal of Mathematics», vol. LVIII, № 2, 1936. [131] 8. Характеристической (представляющей) функцией арифметического предиката P (х1, ..., Хn)называется такая арифметическая функция f, что для любого набора аргументов x1, ..., Хn(х1, ..., Хn) = (1, если предикат P выполняется на данном наборе) или (0, если P не выполняется на данном наборе.) Предикат называется примитивно‑, обще‑ или частично‑рекурсивным в соответствии с типом характеристической функции. [132] 9. В основополагающей статье А. Тьюринга (А. М. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. «Proceedings of the London Mathematical Society», Ser. 2, vol. 42, 1936) была не только изложена его «машина», но и дана попытка проанализировать вычислительный процесс вообще. Обширный фрагмент из этой статьи Тьюринга можно в русском переводе найти в кн.: М. Минскии. Вычисления и автоматы. М., 1971, с. 138–142. Там же читатель найдет подробное описание Тьюринговых машин. Обращаем внимание на то, что наше изложение машины Тьюринга в соответствии с традицией, принятой в современных работах, в ряде непринципиальных пунктов отличается от тьюрингова. — 138 —
|