operador µ - μ operator

Na teoria da computabilidade , a μ-operador , operador de minimização , ou ilimitados busca operador procura o menos número natural com uma determinada propriedade. Adicionar o operador µ aos cinco operadores recursivos primitivos torna possível definir todas as funções computáveis .

Definição

Suponha que R ( y , x 1 , ..., x k ) seja uma relação fixa ( k +1) -ary nos números naturais . O operador µ "μ y ", na forma ilimitada ou limitada, é uma "função teórica dos números" definida a partir dos números naturais para os números naturais. No entanto, "μ y " contém um predicado sobre os números naturais que fornece verdadeiro quando o predicado é satisfeito e falso quando não é.

O operador μ limitado aparece anteriormente em Kleene (1952) Capítulo IX Funções primitivas recursivas, §45 Predicados, representação do fator principal como:

" " (p. 225)

Stephen Kleene observa que qualquer uma das seis restrições de desigualdade no intervalo da variável y é permitida, ou seja, y < z , y ≤ z , w < y < z , w < y ≤ z , w ≤ y < z e w ≤ y ≤ z . "Quando o intervalo indicado não contém y tal que R ( y ) [é" verdadeiro "], o valor da expressão " μ y "é o número cardinal do intervalo" (p. 226); é por isso que o " z " padrão aparece na definição acima. Conforme mostrado abaixo, o μ-operador limitado "μ y y < z " é definido em termos de duas funções recursivas primitivas chamadas de soma finita Σ e produto finito Π, uma função de predicado que "faz o teste" e uma função de representação que converte {t, f} a { 0 , 1 }.

No Capítulo XI §57 Funções Recursivas Gerais, Kleene define o operador μ ilimitado sobre a variável y da seguinte maneira,

" " (p. 279, onde " " significa "existe um y tal que ...")

Nesse caso, o próprio R, ou sua função representativa , fornece 0 quando é satisfeito (ou seja, fornece verdadeiro ); a função então fornece o número y . Não existe limite superior em y , portanto, nenhuma expressão de desigualdade aparece em sua definição.

Para um dado R ( y ), o operador µ ilimitado µ y R ( y ) (observe que não há requisitos para "(E y )") é uma função parcial . Em vez disso, Kleene o faz como uma função total (cf. p. 317):

A versão total do operador μ ilimitado é estudada em matemática reversa de ordem superior ( Kohlenbach (2005) ) da seguinte forma:

onde os sobrescritos significam que n é de ordem zero, f é de primeira ordem e μ é de segunda ordem. Esse axioma dá origem ao sistema dos Cinco Grandes ACA 0 quando combinado com a teoria básica usual da matemática reversa de ordem superior.

Propriedades

(i) No contexto das funções recursivas primitivas , onde a variável de pesquisa y do operador µ é limitada, por exemplo, y < z na fórmula abaixo, se o predicado R é recursivo primitivo (Prova de Kleene #E p. 228), então

μ y y < z R ( y , x 1 , ..., x n ) é uma função recursiva primitiva.

(ii) No contexto das funções recursivas (totais) , onde a variável de pesquisa y é ilimitada, mas existe garantia de existência para todos os valores x i dos parâmetros do predicado recursivo total R,

( x 1 ), ..., ( x n ) (Ey) R ( y , x i , ..., x n ) implica que μ y R ( y , x i , ..., x n ) é um função recursiva total .
Aqui ( x i ) significa "para todo x i " e E y significa "existe pelo menos um valor de y tal que ..." (cf Kleene (1952) p. 279.)

então, os cinco operadores recursivos primitivos mais o operador μ ilimitado, mas total, dão origem ao que Kleene chamou de funções recursivas "gerais" (isto é, funções totais definidas pelos seis operadores de recursão).

(iii) No contexto das funções recursivas parciais : Suponha que a relação R se mantém se e somente se uma função recursiva parcial converge para zero. E suponha que essa função recursiva parcial converge (para algo, não necessariamente zero) sempre que μ y R ( y , x 1 , ..., x k ) é definido ey é μ y R ( y , x 1 , ... , x k ) ou menor. Então a função μ y R ( y , x 1 , ..., x k ) também é uma função recursiva parcial.

O operador µ é usado na caracterização das funções computáveis ​​como funções recursivas µ .

Na matemática construtiva , o operador de pesquisa ilimitado está relacionado ao princípio de Markov .

Exemplos

Exemplo 1: O operador μ limitado é uma função recursiva primitiva

A seguir, x representa a string x i , ..., x n .

O operador μ limitado pode ser expresso simplesmente em termos de duas funções recursivas primitivas (doravante "prf") que também são usadas para definir a função CASE - o produto dos termos Π e a soma dos termos Σ (cf Kleene #B página 224). (Conforme necessário, qualquer limite para a variável, como s ≤ t ou t < z , ou 5 < x <17 etc. é apropriado). Por exemplo:

  • Π s ≤ t f s ( x , s ) = f 0 ( x , 0) × f 1 ( x , 1) × ... × f t ( x , t )
  • Σ t < z g t ( x , t ) = g 0 ( x , 0) + g 1 ( x , 1) + ... + g z-1 ( x , z -1)

Antes de prosseguirmos, precisamos introduzir uma função ψ chamada "a função representativa " do predicado R. A função ψ é definida a partir de entradas (t = "verdade", f = "falsidade") para saídas (0, 1) ( observe a ordem ! ). Neste caso, a entrada para ψ. ou seja, {t, f}. vem da saída de R:

  • ψ (R = t) = 0
  • ψ (R = f) = 1

Kleene demonstra que μ y y < z R ( y ) é definido como segue; vemos que a função produto Π está agindo como um operador booleano OR, e a soma Σ está agindo um pouco como um booleano AND, mas está produzindo {Σ ≠ 0, Σ = 0} em vez de apenas {1, 0}:

μ y y < z R ( y ) = Σ t < z Π s ≤ t ψ (R ( x , t , s )) =
[ψ ( x , 0, 0)] +
[ψ ( x , 1, 0) × ψ ( x , 1, 1)] +
[ψ ( x , 2, 0) × ψ ( x , 2, 1) × ψ ( x , 2, 2)] +
... +
[ψ ( x , z -1, 0) × ψ ( x , z -1, 1) × ψ ( x , z -1, 2) ×. . . × ψ ( x , z -1, z -1)]
Observe que Σ é na verdade uma recursão primitiva com a base Σ ( x , 0) = 0 e a etapa de indução Σ ( x , y +1) = Σ ( x , y ) + Π ( x , y ). O produto Π também é uma recursão primitiva com etapa base Π ( x , 0) = ψ ( x , 0) e etapa de indução Π ( x , y +1) = Π ( x , y ) × ψ ( x , y +1 ) .

A equação é mais fácil se observada com um exemplo, como dado por Kleene. Ele apenas criou as entradas para a função representativa ψ (R ( y )). Ele designou as funções representativas χ ( y ) em vez de ψ ( x , y ):

y 0 1 2 3 4 5 6 7 = z
χ ( y ) 1 1 1 0 1 0 0
π ( y ) = Π s ≤ y χ ( s ) 1 1 1 0 0 0 0 0
σ ( y ) = Σ t < y π ( t ) 1 2 3 3 3 3 3 3
pelo menos y < z tal que R ( y ) é "verdadeiro":
φ ( y ) = μ y y < z R ( y ) 		3

Exemplo 2: O operador μ ilimitado não é recursivo primitivo

O operador µ ilimitado - a função µ y - é aquele comumente definido nos textos. Mas o leitor pode se perguntar por que o operador µ ilimitado está procurando uma função R ( x , y ) para produzir zero , em vez de algum outro número natural.

Em uma nota de rodapé, Minsky permite que seu operador termine quando a função interna produz uma correspondência com o parâmetro " k "; este exemplo também é útil porque mostra o formato de outro autor:
"Para μ t [φ ( t ) = k ]" (p. 210)

A razão para zero é que o operador ilimitado μ y será definido em termos da função "produto" Π com seu índice y permitido "crescer" conforme as pesquisas do operador μ. Conforme observado no exemplo acima, o produto Π x < y de uma sequência de números ψ ( x , 0) *, ..., * ψ ( x , y ) resulta em zero sempre que um de seus membros ψ ( x , i ) é zero:

Π s < y = ψ ( x , 0) *, ..., * ψ ( x , y ) = 0

se algum ψ ( x , i ) = 0 onde 0≤ i ≤ s . Portanto, o Π está agindo como um AND booleano.

A função μ y produz como "saída" um único número natural y = {0, 1, 2, 3, ...}. No entanto, dentro do operador, uma das duas "situações" pode aparecer: (a) uma "função teórica dos números" χ que produz um único número natural, ou (b) um "predicado" R que produz {t = verdadeiro, f = falso}. (E, no contexto de funções recursivas parciais , Kleene posteriormente admite um terceiro resultado: "μ = indeciso".)

Kleene divide sua definição do operador µ ilimitado para lidar com as duas situações (a) e (b). Para a situação (b), antes que o predicado R ( x , y ) possa servir em uma capacidade aritmética no produto Π, sua saída {t, f} deve primeiro ser "operada" por sua função representativa χ para render {0, 1} E para a situação (a), se uma definição deve ser usada, então a função teórica dos números χ deve produzir zero para "satisfazer" o operador µ. Com este assunto resolvido, ele demonstra com uma única "Prova III" que os tipos (a) ou (b) junto com os cinco operadores recursivos primitivos produzem as funções recursivas (totais) , com esta condição para uma função total :

Para todos os parâmetros x , deve ser fornecida uma demonstração para mostrar que existe um y que satisfaça (a) μ y ψ ( x , y ) ou (b) μ y R ( x , y ).

Kleene também admite uma terceira situação (c) que não requer a demonstração de "para todo x a y existe tal que ψ ( x , y )". Ele usa isso em sua prova de que existem mais funções recursivas totais do que podem ser enumeradas ; cf rodapé Demonstração da função total .

A prova de Kleene é informal e usa um exemplo semelhante ao primeiro exemplo, mas primeiro ele transforma o operador µ em uma forma diferente que usa o "produto dos termos" Π operando na função χ que produz um número natural n , que pode seja qualquer número natural e 0 na instância em que o teste do operador u for "satisfeito".

A definição reformulada com a função Π:
μ y y < z χ ( y ) =
  • (i): π ( x , y ) = Π s < y χ ( x , s )
  • (ii): φ ( x ) = τ (π ( x , y ), π ( x , y ' ), y )
  • (iii): τ ( z ' , 0, y ) = y ; τ ( u , v , w ) é indefinido para u = 0 ou v > 0.

Isso é sutil. À primeira vista, as equações parecem estar usando recursão primitiva. Mas Kleene não nos forneceu uma etapa de base e uma etapa de indução da forma geral:

  • etapa base: φ (0, x ) = φ ( x )
  • etapa de indução: φ (0, x ) = ψ (y, φ (0, x ), x )

Para ver o que está acontecendo, primeiro temos que nos lembrar que atribuímos um parâmetro (um número natural) a cada variável x i . Em segundo lugar, vemos um operador-sucessor em ação iterando y (ou seja, y ' ). E em terceiro lugar, vemos que a função μ y y < z χ ( y , x ) está apenas produzindo instâncias de χ ( y , x ), ou seja, χ (0, x ), χ (1, x ), ... até um instância resulta em 0. Quarto, quando uma instância χ ( n , x ) produz 0, ela faz com que o termo do meio de τ, ou seja, v = π ( x , y ' ) produza 0. Finalmente, quando o termo do meio v = 0, μ y y < z χ ( y ) executa a linha (iii) e "sai". A apresentação de Kleene das equações (ii) e (iii) foi trocada para tornar este ponto que a linha (iii) representa uma saída - uma saída tomada apenas quando a pesquisa encontra um y para satisfazer χ ( y ) e o termo do produto médio π ( x , y ' ) é 0; o operador então termina sua pesquisa com τ ( z ' , 0, y ) = y .

τ (π ( x , y ), π ( x , y ' ), y ), ou seja:
  • τ (π ( x , 0), π ( x , 1), 0),
  • τ (π ( x , 1), π ( x , 2), 1)
  • τ (π ( x , 2), π ( x , 3), 2)
  • τ (π ( x , 3), π ( x , 4), 3)
  • ... até que uma correspondência ocorra em y = n e então:
  • τ ( z ' , 0, y ) = τ ( z' , 0, n ) = n e a busca do operador µ é feita.

Para o exemplo Kleene "... considere [s] quaisquer valores fixos de ( x i , ..., x n ) e escreva [s] simplesmente 'χ ( y )' para 'χ ( x i , ..., x n ), y ) '":

y 0 1 2 3 4 5 6 7 etc.
χ ( y ) 3 1 2 0 9 0 1 5 . . .
π ( y ) = Π s ≤ y χ ( s ) 1 3 3 6 0 0 0 0 . . .
↑
pelo menos y < z tal que R ( y ) é "verdadeiro":
φ ( y ) = μ y y < z R ( y ) 		3


Exemplo 3: Definição do operador μ ilimitado em termos de uma máquina abstrata

Ambos Minsky (1967) p. 21 e Boolos-Burgess-Jeffrey (2002) p. 60-61 fornecem definições do operador µ como uma máquina abstrata; veja a nota de rodapé Definições alternativas de µ .

A seguinte demonstração segue Minsky sem a "peculiaridade" mencionada na nota de rodapé. A demonstração usará um modelo de contra-máquina "sucessora" intimamente relacionado aos Axiomas de Peano e às funções recursivas primitivas . O modelo consiste em (i) uma máquina de estado finito com uma TABELA de instruções e um assim chamado 'registro de estado' que iremos renomear "o Registro de Instrução" (IR), (ii) alguns "registros" cada um dos quais pode conter apenas um único número natural e (iii) um conjunto de instruções de quatro "comandos" descritos na tabela a seguir:

A seguir, o simbolismo "[r]" significa "o conteúdo de", e "→ r" indica uma ação em relação ao registrador r.
Instrução Mnemônico Ação no (s) registro (s) "r" Ação no registro de instrução, IR
Registro CLeaR CLR (r) 0 → r [IR] + 1 → IR
Registro de incremento INC (r) [r] + 1 → r [IR] + 1 → IR
Saltar se for igual JE (r 1 , r 2 , z) Nenhum SE [r 1 ] = [r 2 ] ENTÃO z → IR
ELSE [IR] + 1 → IR
Halt H Nenhum [IR] → IR

O algoritmo para o operador de minimização μ y [φ ( x , y )] irá, em essência, criar uma sequência de instâncias da função φ ( x , y ) conforme o valor do parâmetro y (um número natural) aumenta; o processo continuará (consulte a Nota † abaixo) até que ocorra uma correspondência entre a saída da função φ ( x , y ) e algum número pré-estabelecido (geralmente 0). Assim, a avaliação de φ ( x , y ) requer, no início, a atribuição de um número natural a cada uma de suas variáveis x e uma atribuição de um "número de correspondência" (geralmente 0) a um registrador " w ", e um número (geralmente 0) para registrar y .

Nota †: O operador µ ilimitado continuará este processo de tentativa de correspondência ad infinitum ou até que ocorra uma correspondência. Portanto, o registro " y " deve ser ilimitado - ele deve ser capaz de "reter" um número de tamanho arbitrário. Ao contrário de um modelo de computador "real", os modelos de máquina abstratos permitem isso. No caso de um operador μ limitado , um operador μ de limite inferior iniciaria com o conteúdo de y definido como um número diferente de zero. Um operador µ de limite superior exigiria um registro adicional "ub" para conter o número que representa o limite superior mais uma operação de comparação adicional; um algoritmo pode fornecer limites inferior e superior.

A seguir, estamos assumindo que o Registrador de Instrução (IR) encontra a "rotina" μ y na instrução número " n ". Sua primeira ação será estabelecer um número em um registro " w " dedicado - um "exemplo" do número que a função φ ( x , y ) deve produzir antes que o algoritmo possa terminar (classicamente, este é o número zero, mas veja o nota de rodapé sobre o uso de números diferentes de zero). A próxima ação do algoritmo na instrução " n +1" será limpar o registrador " y " - " y " atuará como um "contador ascendente" que começa em 0. Então, na instrução " n +2" o algoritmo avalia sua função φ ( x , y ) - assumimos que isso leva j instruções para realizar - e no final de sua avaliação φ ( x , y) deposita sua saída no registrador "φ". Na instrução ( n + j +3) rd, o algoritmo compara o número no registro " w " (por exemplo, 0) com o número no registro "φ" - se eles forem iguais, o algoritmo foi bem-sucedido e escapa pela saída ; caso contrário, aumenta o conteúdo do " y " registar-se e circula de volta com este novo valor de y para φ função de teste ( x , y ) de novo.

IR Instrução Ação no registro Ação no Registro de Instrução IR
n μ y [φ ( x , y )]: CLR (w) 0 → w [IR] + 1 → IR
n +1 CLR ( y ) 0 → y [IR] + 1 → IR
n +2 ciclo: φ ( x , y ) φ ([ x ], [ y ]) → φ [IR] + j + 1 → IR
n + j +3 JE (φ, w , sair) Nenhum CASO: {SE [φ] = [ w ] ENTÃO sair → IR
OUTRO [IR] + 1 → IR}
n + j +4 INC ( y ) [ y ] + 1 → y [IR] + 1 → IR
n + j +5 JE (0, 0, loop) Salto incondicional CASE: {IF [r 0 ] = [r 0 ] THEN loop → IR
ELSE loop → IR}
n + j +6 saída: etc.

Veja também

Notas de rodapé

Demonstração de função total

O que é obrigatório se a função é para ser uma função total é uma demonstração por algum outro método (por exemplo, indução ) que para cada combinação de valores de seus parâmetros x i algum número natural y irá satisfazer o operador µ de modo que o algoritmo que representa o cálculo pode terminar:

"... devemos sempre hesitar em assumir que um sistema de equações realmente define uma função recursiva geral (ou seja, total). Normalmente exigimos evidências auxiliares para isso, por exemplo, na forma de uma prova indutiva de que, para cada valor de argumento, o cálculo termina com um valor único. " (Minsky (1967) p.186)
“Em outras palavras, não devemos alegar que uma função é efetivamente calculável com base no fato de que ela se mostrou recursiva geral (isto é, total), a menos que a demonstração de que é recursiva geral seja eficaz.” (Kleene (1952) p 0,319)

Para obter um exemplo do que isso significa na prática, consulte os exemplos em funções recursivas mu - mesmo o algoritmo de subtração truncado mais simples " x - y = d " pode resultar, para os casos indefinidos quando x < y , (1) sem terminação, (2 ) sem números (ou seja, algo errado com o formato, de modo que o rendimento não é considerado um número natural), ou (3) engano: números errados no formato correto. O algoritmo de subtração "adequado" requer atenção cuidadosa a todos os "casos"

( x , y ) = {(0, 0), ( a , 0), (0, b ), ( a ≥ b , b ), ( a = b , b ), ( a < b , b )}.

Mas mesmo quando o algoritmo mostrou produzir a saída esperada nas instâncias {(0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2)}, ficamos com uma sensação desconfortável até que possamos conceber uma "demonstração convincente" de que os casos ( x , y ) = ( n , m ) produzem todos os resultados esperados. Para o ponto de Kleene: nossa "demonstração" (isto é, o algoritmo que é nossa demonstração) é convincente o suficiente para ser considerado eficaz ?

Modelos de máquina abstratos alternativos do operador μ ilimitado de Minsky (1967) e Boolos-Burgess-Jeffrey (2002)

O operador µ ilimitado é definido por Minsky (1967) p. 210, mas com uma falha peculiar: o operador-não produzirá t = 0 quando seu predicado (o teste IF-THEN-ELSE) for satisfeito; em vez disso, produz t = 2. Na versão de Minsky, o contador é " t ", e a função φ ( t , x ) deposita seu número no registrador φ. Na definição usual de µ, o registrador w conterá 0, mas Minsky observa que ele pode conter qualquer número k . O conjunto de instruções de Minsky é equivalente ao seguinte, onde "JNE" = Salta para z se diferente:

{CLR ( r ), INC ( r ), JNE ( r j , r k , z )}
IR Instrução Ação no registro Ação no registro de instrução, IR
n μ y φ ( x ): CLR ( w ) 0 → w [IR] + 1 → IR
n + 1 CLR ( t ) 0 → t [IR] + 1 → IR
n +2 ciclo: φ ( y , x ) φ ([ t ], [ x ]) → φ [IR] + j + 1 → IR
n + j +3 INC ( t ) [ t ] + 1 → t [IR] + 1 → IR
n + j +4 JNE (φ, w , loop) Nenhum CASO: {SE [φ] ≠ [ w ] ENTÃO "sair" → IR
ELSE [IR] + 1 → IR}
n + j +5 INC ( t ) [ t ] + 1 → t [IR] + 1 → IR
n + j +6 saída: etc.

O operador µ ilimitado também é definido por Boolos-Burgess-Jeffrey (2002) p. 60-61 para uma máquina de contagem com um conjunto de instruções equivalente ao seguinte:

{CLR (r), INC (r), DEC (r), JZ (r, z), H}

Nesta versão o contador "y" é denominado "r2", e a função f ( x , r2) deposita seu número no registro "r3". Talvez a razão de Boolos-Burgess-Jeffrey limpar r3 seja facilitar um salto incondicional para o loop ; isso geralmente é feito usando um registro dedicado "0" que contém "0":

IR Instrução Ação no registro Ação no registro de instrução, IR
n μ r 2 [f ( x , r 2 )]: CLR ( r 2 ) 0 → r 2 [IR] + 1 → IR
n +1 ciclo: f ( y , x ) f ([ t ], [ x ]) → r 3 [IR] + j + 1 → IR
n +2 JZ ( r 3 , saída) Nenhum SE [ r 3 ] = 0 ENTÃO sair → IR
ELSE [IR] + 1 → IR
n + j +3 CLR ( r 3 ) 0 → r 3 [IR] + 1 → IR
n + j +4 INC ( r 2 ) [ r 2 ] + 1 → r 2 [IR] + 1 → IR
n + j +5 JZ ( r 3 , loop) CASO: {IF [ r 3 ] = 0 THEN loop → IR
ELSE [IR] + 1 → IR}
n + j +6 saída: etc.

Referências

  • Stephen Kleene (1952) Introdução à Metamatemática , North-Holland Publishing Company, Nova York, 11ª reimpressão 1971: (notas da 2ª edição adicionadas na 6ª reimpressão).
  • Kohlenbach, Ulrich (2005), Higher Order Reverse Mathematics, Reverse Mathematics 2001 , Lecture notes in Logic, Cambridge University Press , doi : 10.1017 / 9781316755846.018 , ISBN   9781316755846
  • Marvin L. Minsky (1967), Computation: Finite and Infinite Machines , Prentice-Hall, Inc. Englewood Cliffs, NJ
Nas páginas 210-215 Minsky mostra como criar o operador µ usando o modelo de máquina de registro , demonstrando assim sua equivalência às funções recursivas gerais.