Язык программирования, который может реализовывать только вычислимые биективные функции?

10

Существуют ли языки программирования (или логика), которые могут реализовать (или выразить) функцию тогда и только тогда, когда f вычислимые биективные функции?f:NNf

Чао Сюй
источник
Кто-то доказал мне, что невозможно создать язык, который принимает только завершающие программы. Так как ваш вопрос довольно похож, наверное, нет.
FUZxxl
1
Кажется маловероятным, чтобы существовал такой язык программирования, я думаю, вы могли бы попытаться применить его, но тогда вы не сможете выполнять простые вещи, такие как сортировка, по крайней мере, без того, чтобы он не стал ужасно сложным и болезненным.
Люк Мэтисон
@FUZxxl Это не захватывает много завершающих программ, фактически даже функцию f (x) = 1 невозможно выразить на этом языке. Кроме того, у меня есть ощущение, что этот вид функций захвачен полным функциональным программированием, поскольку каждая функция является полной функцией.
Чао Сюй
@ FUZxxl, я не думаю, что это правильно, но такой язык должен быть ограничен. Например, язык, который был бы эквивалентен конечным детерминированным автоматам, гарантированно заканчивался, но был бы чрезвычайно ограничен в том, что он мог вычислить.
2012 года
@FUZxxl, детали такого заявления важны. Легко спроектировать язык программирования, на котором заканчивается каждая программа. Другое дело спроектировать язык, который мы можем выразить каждой вычислимой функцией.
Виджей Д

Ответы:

9

Там нет такого языка.

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

NN

f0,f1,f2,

g:NNg(2k)g(2k+1)fk(2k)

  • fk(2k)=2kg(2k)=2k+1g(2k+1)=2k
  • fk(2k)2kg(2k)=2kg(2k+1)=2k+1

kNgfkg(2k)fk(2k)g

Андрей Бауэр
источник
2k2k+1g(k)=fk(k)+1
fk(k)+1
g
Первоначальное утверждение неверно, в литературе много таких языков.
Натаниэль
С другой стороны, ваше доказательство кажется законным. Возможно, я как-то запутался. Мне нужно внимательно прочитать статью Аксельсена и Глюка (см. Мой ответ), чтобы понять, что здесь происходит.
Натаниэль