Teorema Sm n

Sm n theorem In computability theory the S m n theorem, (também chamado de lema da tradução, teorema do parâmetro, e o teorema de parametrização) é um resultado básico sobre linguagens de programação (e, De forma geral, numerações de Gödel das funções computáveis) (Sol 1987, Roger 1967). Foi provado pela primeira vez por Stephen Cole Kleene (1943). The name S m n comes from the occurrence of an S with subscript n and superscript m in the original formulation of the theorem (Veja abaixo).

Em termos práticos, o teorema diz que para uma dada linguagem de programação e inteiros positivos m e n, there exists a particular algorithm that accepts as input the source code of a program with m + n free variables, juntamente com m valores. Este algoritmo gera código-fonte que substitui efetivamente os valores das primeiras m variáveis ​​livres, deixando o resto das variáveis ​​livres.

Conteúdo 1 Detalhes 2 Declaração formal 3 Exemplo 4 Veja também 5 Referências 6 External links Details The basic form of the theorem applies to functions of two arguments (Pessoas 2009, p. 6). Dada uma numeração de Gödel {estilo de exibição varphi } de funções recursivas, existe uma função recursiva primitiva s de dois argumentos com a seguinte propriedade: para cada número de Gödel p de uma função computável parcial f com dois argumentos, as expressões {estilo de exibição varphi _{s(p,x)}(y)} e {estilo de exibição f(x,y)} são definidos para as mesmas combinações de números naturais x e y, e seus valores são iguais para qualquer combinação. Em outras palavras, a seguinte igualdade extensional de funções vale para todo x: {estilo de exibição varphi _{s(p,x)}simeq lambda y.varphi _{p}(x,y).} De forma geral, para qualquer m, n > 0, existe uma função recursiva primitiva {estilo de exibição S_{n}^{m}} of m + 1 arguments that behaves as follows: for every Gödel number p of a partial computable function with m + n arguments, e todos os valores de x1, …, xm: {estilo de exibição varphi _{S_{n}^{m}(p,x_{1},pontos ,x_{m})}mesmo lambda y_{1},pontos ,s_{n}.varphi_{p}(x_{1},pontos ,x_{m},s_{1},pontos ,s_{n}).} A função s descrita acima pode ser considerada {estilo de exibição S_{1}^{1}} .

Formal statement Given arities {estilo de exibição m} e {estilo de exibição m} , para cada máquina de Turing {estilo de exibição {texto{MT}}_{x}} de aridade {estilo de exibição m+n} e para todos os valores possíveis de entradas {estilo de exibição y_{1},pontos ,s_{m}} , existe uma máquina de Turing {estilo de exibição {texto{MT}}_{k}} de aridade {estilo de exibição m} , de tal modo que {estilo de exibição para todos z_{1},pontos ,z_{n}:{texto{MT}}_{x}(s_{1},pontos ,s_{m},z_{1},pontos ,z_{n})={texto{MT}}_{k}(z_{1},pontos ,z_{n}).} Além disso, existe uma máquina de Turing {estilo de exibição S} que permite {estilo de exibição k} ser calculado a partir {estilo de exibição x} e {estilo de exibição y} ; é denotado {estilo de exibição k=S_{n}^{m}(x,s_{1},pontos ,s_{m})} .

Informalmente, {estilo de exibição S} encontra a Máquina de Turing {estilo de exibição {texto{MT}}_{k}} que é o resultado de codificar os valores de {estilo de exibição y} em {estilo de exibição {texto{MT}}_{x}} . O resultado generaliza para qualquer modelo de computação Turing-completo.

Example The following Lisp code implements s11 for Lisp.

(defun s11 (f x) (deixar ((y (gensym))) (lista 'lambda (lista y) (lista f x y)))) Por exemplo, (s11'(lambda (xy) (+ xy)) 3) avalia para (lambda (g42) ((lambda (xy) (+ xy)) 3 g42)).

Veja também Currying Teorema da recursão de Kleene Avaliação parcial Referências Kleene, S. C. (1936). "Funções recursivas gerais de números naturais". Anais Matemáticos. 112 (1): 727–742. doi:10.1007/BF01565439. Kleene, S. C. (1938). "Sobre notações para números ordinais" (PDF). O Diário da Lógica Simbólica. 3: 150-155. (Esta é a referência que o 1989 edição de Odifreddi "Teoria da Recursão Clássica" gives on p. 131 for the {estilo de exibição S_{n}^{m}} teorema.) Pessoas, UMA. (2009). Computabilidade e aleatoriedade. Guias de lógica de Oxford. Volume. 51. Oxford: imprensa da Universidade de Oxford. ISBN 978-0-19-923076-1. Zbl 1169.03034. Odifreddi, P. (1999). Teoria da Recursão Clássica. Holanda do Norte. ISBN 0-444-87295-7. Roger, H. (1987) [1967]. A Teoria das Funções Recursivas e Computabilidade Eficaz. Primeira edição em brochura de imprensa do MIT. ISBN 0-262-68052-1. Sol, R. (1987). Conjuntos e graus recursivamente enumeráveis. Perspectivas em Lógica Matemática. Springer-Verlag. ISBN 3-540-15299-7. Weissstein esquerdo externo, Eric W. "Teorema s-m-n de Kleene". MathWorld. Categorias: Teoria da computabilidadeTeoremas em teoria da computaçãoArtigos com exemplo Lisp (linguagem de programação) código