Как записать перечисление всех вычислимых функций?
Числа являются также объектами. Таким образом, можно сделать интересный материал как:
// convert to base 2
(5).toString(2) // returns "101"
// provide built in iteration
Number.prototype.times = function(funct){
if(typeof funct === 'function') {
for(var i = 0;i < Math.floor(this);i++) {
funct(i);
}
}
return this;
}
(5).times(function(i){
string += i+" ";
});
// string now equals "0 1 2 3 4 "
var x = 1000;
x.times(function(i){
document.body.innerHTML += '<p>paragraph #'+i+'</p>';
});
// adds 1000 parapraphs to the document
7 ответов
То, что вам нужно, называется интерпретатором.
Во-первых, любое перечисление со свойствами, которые вам нужны, не будет соответствовать интересным функциям, которыми вы хотите манипулировать в первых 2 ^ 32, или даже первые 2 ^ 64, целые числа. Так что вам понадобятся целые числа большего размера, выделенные где-то в памяти и на которые будет ссылаться указатель.
Почему бы тогда не использовать массивы символов (строк), представляющие программу в любом существующем синтаксисе?
Считайте такую строку целым числом, если это вас радует. Номер функции для вычисления f1 () + f2 () - это строка, состоящая из (представления f1), «+» и (представления f2). Вы уловили идею ...
Чего в этом подходе нет, так это уникальности представления функции, которая, возможно, подразумевалась в вашем вопросе (я не уверен). В чем я уверен, так это в том, что уникальность представления несовместима с наличием простых или даже вычислимых операций композиции над представлениями функций - например, было бы легкое решение проблемы остановки, если бы это не было так.
Хотя перечислить все возможные выражения на каком-то языке не так уж сложно, вы не сможете ограничить их теми выражениями, которые обозначают завершающие функции .
Но если вас не интересует завершение, использование комбинаторов (с добавлением некоторых арифметических примитивов для полезности) может быть лучшим способом, поскольку вы избегаете вводить имена переменных таким образом.
непростой вопрос. Я думаю, вам нужно начать с генератора функций, который может генерировать все функции одну за другой. Это приведет к перечислению.
Поскольку вам приходится иметь дело с множеством бесконечных измерений ... давайте подумаем об этом.
Давайте сведем проблему к функциям с n параметрами и базовыми операциями +, -, *, / .
Давайте построим все функции с помощью одной операции:
a + a
a + b
а - а
а - б
а * а
a * b
а / а
a / b
Думаю, легко увидеть, что некоторые из этих функций имеют больше смысла, чем другие, а некоторые из них могут быть равными, но, по крайней мере, это отображение, которое можно сгенерировать с помощью цикла.
Теперь, в следующей итерации, можно легко добавить к каждой из этих функций
- один из уже существующих параметров со всеми операциями
- третий параметр со всеми операциями
После этого у вас будет огромный список функций, для которых вы можно повторить шаг 2.
Так как это функция, которая оценивает все более сложные функции, такие как sin и log (ряд Тейлора), они также должны быть включены в это пространство функций.
Помогает ли это? Не стесняйтесь редактировать этот пост!
Просто перечитайте свой пост. Если вы хотите один раз перечислить все программные функции, а не только числовые, думаю, это будет сложнее. Думаю, тогда было бы разумно работать с отображением «функция <-> число», заархивировав источник вашей функции и обработав zip-файл как большое число. И наоборот, вы можете попробовать распаковать любое число и посмотреть, создаст ли он полезную функцию :-) Но я думаю, у вас будет много чисел, которые даже не являются zip-файлами.
Но это удовлетворило бы ваше требование, что для у каждой функции есть номер, который ее представляет: -)
Чтобы написать такую функцию, можно взять любой полный по Тьюрингу язык (компилятор языка программирования, лямбда исчисление, машины Тьюринга ...) и перечислить все программы
Я не очень уверен, можно ли это вообще сделать ... Похоже, это противоречит тезису Тьюринга-Чёрча. Чтобы перечислить все программы, сначала вам понадобится алгоритм, который определяет, какие программы допустимы, а какие нет, а это невозможно ... Если только вы не заботитесь об этом и не разрешаете некорректные программы на вашем языке.
Но, возможно, вам может помочь Годелизация формальной системы ... Я бы попробовал с Лиспом, наличие кода в виде данных могло бы очень помочь.
Не уверен, что понимаю. Одно но - вы не можете перечислить все возможные вычислимые функции. Короткий ответ: потому что иначе будет универсальный антивирус. Длинный ответ: потому что, если бы было такое перечисление, в этом наборе была бы также функция, которая вычисляет само перечисление. Как парадокс Рассела.
Другой ответ на ваш вопрос был бы - вы хотите «перечислить» все возможные вычислимые функции; для этого вы можете представить их как простые числа и использовать их композицию как умножение. Это гарантирует уникальность. Факторизация даст вам обратную функцию.
Вы можете взять любой язык программирования, чтобы определить, является ли что-то программой или нет, и перечислить все программы в лексикографическом порядке. Чтобы избежать хотя бы небольшого комбинаторного взрыва, вы можете присвоить определенные пользователем имена (переменные, функции и т. Д.) В нормализованной форме. Очевидно, это приведет к появлению огромного количества функций, и будет нелегко выбрать, какие из них действительно полезны. Любой автоматический метод обрезки либо исключит некоторые функции, которые вам действительно понадобятся, либо не сможет обрезать комбинаторный взрыв настолько, чтобы он был полезен, либо и то, и другое.
Другой недостаток состоит в том, что это будет очень сложно. перейти от числа к функции: трудно найти лучший способ найти функцию 433,457,175,432,167, 463, чем перечислить около четырехсот квадриллионов функций.
Другой способ - закодировать функцию в число, сопоставив символы с числами и эффективно объединяя их.
Предположим, что это символы +, -,: = , ==, <, if, затем, endif, do, end_do_condition, enddo и разделитель операторов. Это 11 символов, без переменных, для довольно минимального набора, который не включает ничего похожего на вызов функции и требует, чтобы вы умножали и делили себя. (На самом деле я не уверен, что это сработает без одного или двух логических операторов.) Добавьте пять имен переменных, и вы получите язык программирования с 4-битными символами. Это означает, что в 64-битное целое число без знака уместится максимум шестнадцать символов.
Как только вы это получите, все возможные отношения между функциями будут представлены в виде арифметического отношения, но чрезвычайно сложного, которое будет очень сложно реализовать на практике.
Короче говоря, хотя это теоретически возможно, это будет далеко слишком коряво на практике. Вероятно, было бы проще написать интерпретатор функционального языка на выбранном вами нефункциональном языке.
Как сказал Паскаль, вам нужен интерпретатор, но можно сделать даже лучше: использовать процессор как интерпретатор напрямую.
Подайте число N (скажем, как некоторый большой массив int ) непосредственно в буфер и выполнить этот буфер как машинный код.
Для каждой возможной функции, которую ваш компьютер может выполнить, существует N. К сожалению. не все N являются действующей программой (это не запрашивалось) или завершающей программой (что невозможно).
С другой стороны, эта функция создаст такие жемчужины, как World of Warcraft, Microsoft Office 17, включая Service Pack 6 и Windows 9.