O teorema do smn é o mesmo conceito que o curry?

Estou estudando o teorema do smn e o conceito me lembrou de currying.

Do artigo da wikipedia sobre o teorema do smn :

o teorema diz que, para uma dada linguagem de programação e números inteiros positivos m e n, existe um algoritmo específico que aceita como entrada o código fonte de um programa com m + n variáveis livres, juntamente com valores m. Este algoritmo gera código fonte que efetivamente substitui os valores das primeiras m variáveis livres, deixando o restante das variáveis livres.

De um artigo sobre curry :

Intuitivamente, o currying diz "se você corrigir alguns argumentos, terá uma função dos argumentos restantes"

Parece a mesma ideia para mim. A única razão pela qual não tenho certeza é que os materiais que encontrei no smn não mencionam curry (e vice-versa), então eu queria consultá-lo para garantir que realmente o recebesse.

computability emanek
fonte

De fato. Algumas provas de computabilidade têm um sabor lambdish. O teorema smn, de maneira bem aproximada, permite fingir que índices de funções recursivas são termos lambda, de modo que dados

ϕ_{i} (-, -)

$\phi_i(-,-)$ , podemos elaborar o informal

e de acordo com a reivindicação que

é recursivo primitivo. Até a segunda prova do teorema da recursão (que explora smn) é o combinador de pontos fixos da Igreja disfarçado, escondido atrás de

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

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

g

$g$

s ()

$s()$ usos. O ponto principal aqui é que, mesmo que a enumeração

seja definida enumerando, digamos, TMs (ou Java ou ...), ainda podemos fingir que temos lambdas!

ϕ_{i}

$\phi_i$

chi

Bem, o smn faz uma declaração existencial enquanto a existência de uma função ao curry fornece o "compilador". Mas a ideia é a mesma.

Raphael

Respostas:

Sim, é a mesma coisa.

Currying é um conceito do calcculus. É uma transformação entre e $\lambda$ $A \times B \to C$ . Pense nisso como "se tivermos uma função de dois argumentos dos tipos e , podemos corrigir o primeiro argumento (do tipo ) e obteremos uma função do argumento restante (do tipo )". De fato, essa transformação é um isomorfismo. Isso é feito matematicamente preciso por modelos matemáticos de cálcio(digitado), que sãocategorias fechadas cartesianas. $A \to (B \to C)$ $A$ $B$ $A$ $B$ $\lambda$

Há uma categoria de conjuntos numerados. Um conjunto numerado é um par onde é um conjunto e é uma exceção parcial , ou seja, um mapa de números para $(A, \nu_A)$ $A$ $\nu_A : \mathbb{N} \to A$ $A$ , que também pode ser indefinido. Se então dizemos que é um código de . Na teoria da computabilidade, existem muitos exemplos. Sempre que codificamos algumas informações com um número, obtemos um conjunto numerado. Por exemplo, existe uma numeração padrão $\nu_A(n) = x$ $n$ $x$ de funções calculáveis parciais, de modo que é o número calculado pela função calculável parcial codificado por quando aplicada a . (O resultado pode ser indefinido.) $\varphi$ $\varphi_n(k)$ $n$ $k$

Um morfismo de conjuntos numerados é um mapa realizado , o que significa que existe tal que $f : (A, \nu_A) \to (B, \nu_B)$ $n \in \mathbb{N}$ para todos os no domínio de . Isso parece complicado, mas tudo o que diz é que $f(\nu_A(k)) = \nu_B(\varphi_n(k))$ $k$ $\nu_A$ $\varphi_n$ faz para codificar o que faz para elementos. É a maneira matemática de dizer que "programa de implementa a função de ". $f$ $\phi_n$ $f$

Aqui está o argumento final: a categoria de conjuntos numerados é fechada cartesiana. Podemos, portanto, interpretar o calulus digitado nele e perguntar qual programa implementa a operação de curry. A resposta é: o programa dado pelo teorema smn. $\lambda$

Andrej Bauer
fonte

Interessante. Essa categoria está intimamente relacionada a

parece induzir um PER.

P E R (A)

$PER(A)$

ν_{A}

$\nu_A$

chi

Sim, as duas categorias são equivalentes e a terceira versão equivalente é a de conjuntos modestos (consulta "conjuntos e montagens modestos").

Andrej Bauer