Написание программы, которая пишет программу

Question

В теоретической информатике хорошо известно, что программа "Hello world tester" является неразрешимой проблемой. (Вот ссылка, которую я имею в виду под hello world tester
Мой вопрос с тех порВ качестве входных данных программы мы не можем сказать, что будет делать программа, можем ли мы решить обратную проблему:
При заданном наборе входных и выходных данных существует ли алгоритм для написания программы, которая пишет программу для ее достижения?на одно отображение между заданным входом и выходом.
Я знаю о метапрограммировании , но мой вопрос представляет больше теоретический интерес. Что-то, что может применяться для общего случая.

Answer 1

С такими размышлениями нужно быть очень осторожным. Большая путаница возникает из-за непонятного различия между программой x, для которой выполняется предложение P(x) или любой программой x, для которой выполняется предложение P(x). Пока набор программ, для которых выполняется P(x), конечен, всегда есть доказательство их правильности (хотя это доказательство может быть неизвестно).

В этот момент вы также должны различать программы, которые известны и могут быть известны, и программы, которые могут быть показаны только при полном перечислении всех возможностей. Давайте сделаем пример:

Взять 10 программ, которые не принимают и могут или не могут завершить работу и создать "Hello World". Затем есть программа, которая решает, какие из этих программ правильные, а какие нет. Давайте назовем эти программы (x_1,...,x_10). Затем возьмите программы (X_0,...,X_{2^10}), где X_i выведите true для программы x_j, если установлен j-й бит в двоичном представлении i. Одна из этих программ должна быть той, которая решает правильно для всех десяти x_i, просто не может быть никакого способа выяснить, какая из этих 100 X_j s является правильной (мета-проблема в этом точка). * +1021 *

Это говорит о том, что с учетом конечных наборов программ и пар ввода / вывода всегда можно разрешить полное перечисление, и все парадоксы типа проблемы остановки мгновенно исчезают. В вашем случае набор сгенерированных программ для каждого ввода имеет размер один, а набор пар ввода / вывода имеет конечный размер (потому что вы должны предоставить его в метапрограмму). Следовательно, полное перечисление решает вашу проблему очень просто, и вы также можете легко доказать правильность исправленной программы, а также правильность метапрограммы.

Примечание: Поскольку набор сгенерированных программ бесконечен, это один из немногих случаев, когда вы можете доказать P(x) для бесконечного набора программ (на самом деле вы можете доказать P(x,input,output) для этого набора). Это показывает, что множество, являющееся бесконечным, является лишь необходимым, а не достаточным условием для появления парадоксов этого типа.

Answer 2

Ваш вопрос сформулирован неоднозначно.

Как бы вы указали «что должна делать программа»?
Любая точная, полная и машиночитаемая спецификация функциональности программы уже является программой.

Таким образом, ответ на ваш вопрос: компилятор .

---

---

Теперь вы спрашиваете, как найти функцию на основе примераего ввода и вывода.
Это вопрос о статистическом анализе, на который я не могу ответить.

Answer 3

Вопрос недостаточно уточнен, поскольку вы не сказали, как представлены входные и выходные данные.Для конечных списков ответ «да», как в этом коде Python:

def f(input,output):
    print "def g():"
    print "    x = {" + ",".join(repr(x) + ":" + repr(y) for x,y in zip(input,output)) + "}"
    print "    print x[raw_input()]"


>>> f(['2','3','4'],['a','b','x'])
def g():
    x = {'2':'a','3':'b','4':'x'}
    print x[raw_input()]
>>> def g():
...     x = {'2':'a','3':'b','4':'x'}
...     print x[raw_input()]
... 
>>> g()
3
b

для бесконечных множеств, как вы собираетесь их представлять?Если вы показываете только небольшую выборку ввода, это не определяет весь алгоритм.Угадай, что лучшая подгонка является неразрешимой.Если у вас есть «волшебный черный ящик», то существует множество сопоставлений, но только счетное количество программ, поэтому это невозможно.

Answer 4

Зависит от того, что вы подразумеваете под «однозначным отображением».(А также, я полагаю, «вход» и «выход».)

Я предполагаю, что вы спрашиваете, можно ли с помощью примера входов и выходов для данной произвольной программы разработать алгоритмнаписать эквивалентную программу?Если так, ответ - нет.Например, у вас могла бы быть программа с входами / выходами 1/1, 2/2, 3/3, 4/4, и все же, если бы следующее входное значение было 5, выход был бы 3782. Нет никакого способазнать из данного набора результатов, каким может быть следующий результат.

Answer 5

Звучит так, будто вы хотите сгенерировать конечный автомат, который обучается, получая входную последовательность, а затем обновляет себя для получения соответствующей выходной последовательности. Предполагая, что ваши выходные последовательности всегда одинаковы для одной и той же входной последовательности, она должна быть достаточно простой для записи. Если ваши выходные данные не являются детерминированными, например, изменение выходных данных в зависимости от времени суток, вы не можете автоматически сгенерировать конечный автомат.

Answer 6

Я думаю, что я согласен с SLaks, но если взять вещи под другим углом, что делает компилятор?

(EDIT: я вижу, SLaks отредактировал свой оригинальный ответ, который по сути был "вы описываетефункция идентификации ').

Она берет программу на одном исходном языке, которая описывает предполагаемое поведение программы, и "пишет" другую программу на целевом языке, которая демонстрирует такое поведение.

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

Но, основываясь на вашем вопросе, очень трудно сказать, какое из них вы имели в виду, если таковые имеются.