Написание универсальной рекурсивной функции [закрыто]

9

Существует ли короткая явная конструкция универсальной рекурсивной функции ? Все определения, которые я видел, каким-то образом связаны с нумерацией машин Тьюринга, что возможно, но кажется трудным и неуправляемым для написания на языке программирования более высокого уровня (например, Python, Haskell и т. Д.).

lo.logic computability pl.programming-languages sdcvvc
источник
Вопрос был изначально задан в SO , кажется более подходящим здесь.
sdcvvc 22.10.10
1
Насколько я понимаю, универсальная рекурсивная функция в точности дает определенную нумерацию рекурсивных функций (или, что то же самое, машин Тьюринга), чтобы результат можно было вычислить на основе индекса рекурсивной функции и входных данных. Поэтому «универсальная рекурсивная функция без нумерации машин Тьюринга» не кажется мне правдоподобной.
Цуёси Ито
3
Не исследовательский уровень. Любой интерпретатор для полного по Тьюрингу языка является универсальной рекурсивной функцией.
Уоррен Шуди

Ответы:

13

Конечно. Напишите подпрограммы, которые вычисляют каждую из примитивных рекурсивных функций Годеля , и напишите подпрограмму для неограниченного оператора поиска. Набор функций, которые вы можете вычислить таким образом, эквивалентен набору функций, которые могут вычислять машины Тьюринга. Больше информации здесь .

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

Аарон Стерлинг
источник
10

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

Нумерация Годеля существует, но неявно. Например, код C ++, вычисляющий рекурсивную функциюg это индекс для g,

Кава
источник
Интерпретатор для машин Тьюринга (или машин регистра, или рекурсивных функций) также является универсальной рекурсивной функцией, и их нетрудно реализовать. Я реализовал их в C ++ несколько лет назад, и я уверен, что в Python это будет еще проще. Используйте Google, есть много бесплатных симуляторов в Интернете, и некоторые из них даже с открытым исходным кодом.
Каве
8

Универсальная функция uможет быть написана довольно легко на языке, похожем на Haskell (без побочных эффектов, функций высшего порядка), а именно:

u f x = f x

Эта функция uуниверсальна, потому что она принимает (описание) программу fи ленту ввода xи сообщает вам результат запуска fнаx .

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

Андрей Бауэр
источник
Однако uберет функцию - я бы назвал ее функцией более высокого порядка. Я хотел бы uвзять целое число или обычный алгебраический тип данных. Я не навязываю какую-либо конкретную модель вычислений, пока аргумент to uявляется осязаемым - например, он может быть сериализован из / в строку.
sdcvvc
На реальной машине (после компиляции кода) uпроисходит замыкание, представляющее собой конечную последовательность байтов. Даже в обычной теореме utm целое число, которое uпринимает, представляет функцию.
Андрей Бауэр
5

Проверьте также эту статью Джона Тромпа, используя комбинаторную логику. Более ранняя рецензия, по-видимому, более недоступна, была даже аккуратнее.

Юваль Фильмус
источник