Является ли теорема smn тем же понятием, что и карри?

Я изучаю теорему SMN, и концепция напомнила мне о карри.

Из википедии статьи о теореме SMN :

теорема утверждает, что для данного языка программирования и целые положительные числа т и п, существует определенный алгоритм, который принимает в качестве входных данных исходный код программы с т + п свободных переменных, вместе с т значений. Этот алгоритм генерирует исходный код, который эффективно подставляет значения для первых m свободных переменных, оставляя остальные переменные свободными.

Из статьи о карри :

Интуитивно, карри говорит: «Если вы исправите некоторые аргументы, вы получите функцию от оставшихся аргументов»

Похоже, та же идея для меня. Единственная причина, по которой я не уверен, состоит в том, что в материалах, с которыми я столкнулся на smn, не упоминается карри (и наоборот), поэтому я хотел проконсультироваться с ним, чтобы убедиться, что я действительно его получаю.

computability emanek
источник

Действительно. У некоторых доказательств вычислимости есть лямбда-аромат. Теорема smn, очень грубо, позволяет сделать вид, что индексы рекурсивных функций являются лямбда-терминами, так что с учетом мы можем создать неформальный и утверждают, что является примитивно-рекурсивной. Даже вторым доказательством теоремы рекурсии (который использует smn) является замаскированный комбинатор Черча с фиксированной точкой, скрытый за использованием . Ключевым моментом здесь является то, что даже если перечисление определено перечисляя, скажем, ТМ (или Java, или ...), мы все равно можем притворяться, что у нас есть лямбды!

ϕ_{i} (-, -)

$\phi_i(-,-)$

g (x) = # λ y . ϕ_{i} (x, y)

$g(x) = \#\lambda y. \phi_i(x,y)$

g

$g$

s ()

$s()$

ϕ_{i}

$\phi_i$

Чи

Ну, smn делает экзистенциальное утверждение, в то время как существование функции с карри обеспечивает «компилятор». Но идея та же самая.

Рафаэль

Ответы:

Да, это то же самое.

Карринг - это понятие из -calculus. Это преобразование между и . Думайте об этом как «если у нас есть функция двух аргументов типов и , то мы можем исправить первый аргумент (типа ), и мы получим функцию от оставшегося аргумента (типа )». Фактически это преобразование является изоморфизмом. Это сделано математически точным с помощью математических моделей (типизированных) -calculus, которые являются декартовыми замкнутыми категориями . $\lambda$ $A \times B \to C$ $A \to (B \to C)$ $A$ $B$ $A$ $B$ $\lambda$

Существует категория пронумерованных наборов. Нумерованный набор - это пара где - набор, а - частичная выборка, т. Карта из чисел на , которая также может быть неопределенной. Если , то мы говорим , что является кодом из . В теории вычислимости есть много примеров. Всякий раз, когда мы кодируем некоторую информацию числом, мы получаем пронумерованный набор. Например, существует стандартная нумерация частично вычислимых функций, так что - это число, вычисляемое частичной вычислимой функцией, закодированной $(A, \nu_A)$ $A$ $\nu_A : \mathbb{N} \to A$ $A$ $\nu_A(n) = x$ $n$ $x$ $\varphi$ $\varphi_n(k)$ $n$ применительно к . (Результат может быть неопределенным.) $k$

Морфизм нумерованных множеств - это реализованное отображение , что означает, что существует такое, что для всех в области . Это выглядит сложно, но все, что он говорит, это то, что делает с кодами то, что делает с элементами. Это математический способ сказать, что «программа реализует функцию ». $f : (A, \nu_A) \to (B, \nu_B)$ $n \in \mathbb{N}$ $f(\nu_A(k)) = \nu_B(\varphi_n(k))$ $k$ $\nu_A$ $\varphi_n$ $f$ $\phi_n$ $f$

Вот изюминка: категория пронумерованных множеств является декартовой замкнутой. Поэтому мы можем интерпретировать в нем напечатанный -calulus и спросить, какая программа реализует операцию каррирования. Ответ: программа, заданная теоремой smn. $\lambda$

Андрей Бауэр
источник

Интересный.

категория тесно связана с

кажется , чтобы вызвать PER.

P E R (A)

$PER(A)$

ν_{A}

$\nu_A$

Чи

Да, две категории эквивалентны, а третья эквивалентная версия - это скромные наборы (поиск «скромные наборы и сборки»).

Андрей Бауэр