Математическая энциклопедия - трансляция программ

1) Т. п. в программировании, компиляция программ,систематический процесс, который любую программу ip на входном алгоритмическом языкеLI преобразует в некоторую программу ор на объектном языке LO, при итом так, что обе программы, ip и ор, реализуют одну и ту же функцию, то есть если d - входные данные программы, то ip(d) = op(d).

2) Т. п. в теории вычислимых функций и алгоритмов теориилюбое отображение одной нумерации вычислимых функций в другую, сохраняющее свойство образа и прообраза быть номером одной и той же функции (наличие эффективного транслирующего отображения наз. также сводимостью одной нумерации к другой).

В практике программирования обычно входным языком является программирования язык, используемый человеком, а объектным языком язык непосредственно выполняемых машинных программ. Сама Т. п., как правило, совершается автоматически, то есть с помощью программы tна нек-ром языке реализации LR, наз. транслятором (или компилятором), то есть t(ip)=op. Систематич. разработка трансляторов для любого входного языка LI из нек-рого класса языков составляет содержание автоматизации программирования, а соответствующие средства такой разработки наз. системами построения трансляторов или трансляторами трансляторов, При этом язык реализации либо включает объектный язык, либо совпадает с ним:

Понятие Т. п. (сводимости) в теории вычислимых функций приводит к понятию главных нумераций, то есть таких, к к-рым сводятся любые другие нумерации из нек-рого класса. Доказано существование главных вычислимых нумераций у всех конкретных моделей вычислимых функций, в частности у частично рекурсивных функций и у машин Тьюринга. В свою очередь, существование главных вычислимых нумераций взаимообусловлено способностью вычислимых функций к т. н. частичным вычислен и-я м, то есть существованием общерекурсивной функции (в программировании частичного вычислителя, в теории вычислимых функций s-т-n-функции) такой, что если универсальная функция для вычислимых функций ппеременных, то для любой вычислимой функции Fот т+п переменных и с номером NF имеет место тождество

Как видно из тождества, частичный вычислитель по программе функции т+n переменных и по заданным значениям га переменных строит программу функции ппеременных, получаемой из исходной связыванием тее аргументов этими значениями. Результат работы частичного вычислителя наз. проекцией программы NF на заданные значения x1, . . ., х т ее таргументов. Существование главных вычислимых нумераций (см. |1], гл. 1, з 2) и частичных вычислителей (см. [2], з 65), а также взаимной связи между ними (см. [3], з 11, теорема 3) является одной из фундаментальных сторон теории вычислимых функций.

Между задачами практич. трансляции в программировании и частичными вычислениями существует непосредственная связь (см. [4]). Пусть язык реализации LR обладает главной вычислимой нумерацией, и пусть NS - программа частичного вычислителя для LR, выраженная на этом же языке. Пусть, далее, входной язык LI задается программой NLI своей универсальной функции, выраженной на объектном подмножестве LO языка LR, то ecть NLI(ip, d)=ip(d). (В программировании такая программа наз. интерпретатором входного языка.) Тогда справедливы следующие соотношения:

то есть объектная программа это проекция интерпретатора входного языка на входную программу; транслятор это проекция частичного вычислителя на интерпретатор входного языка, а транслятор трансляторов это проекция частичного вычислителя па самого себя.

Лит.:[1] Ершов Ю. Л., Теория нумераций, М., 1977; [2] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; [3] Успенский В. А., Лекции о вычислимых функциях, М., 1960; [4] Ершов А. П., а кн.: Всесоюзная конференция. Методы математической логики в проблемах искусственного интеллекта и систематическое программирование, Паланга, 3-5 сент. 1980, ч. 2, Вильнюс, 1980, с. 26-55.

А. П. Ершов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985