Operador µ

Em Teoria da computabilidade, o operador μ ou operador de minimização procura pelo menor número natural com uma dada propriedade. Adicionando o μ-operador aos cinco operadores primitivos recursivos, é possivel definir todas as funções de computabilidade (dado que a tese de Church-Turing é verdadeira).

Definição

Suponha que R( y, x₁, . . ., x_k ) é uma relação fixa k+1-aria sobre os números naturais. O operador "μy", tanto na forma limitada quanto na ilimitada, é uma "função teórica numeral" definida dos números naturais { 0, 1, 2, ... }. para os números naturais. Contudo, "μy" contém um predicado sobre os números naturais que fornece verdadeiro quando o predicato é satisfeito e falso quando não é.

O mu limitado aparece mais cedo em Kleene (1952) Chapter IX Primitive Recursive Functions, §45 Predicates, prime factor representation como:

"$\mu y_{y<z}R(y).\ \ {\mbox{O mínimo}}\ y<z\ {\mbox{tal que}}\ R(y),\ {\mbox{se}}\ (\exists y)_{y<z}R(y);\ {\mbox{caso contrário}},\ z.$" (p. 225)

Stephen Kleene nota que qualquer uma das seis restrições de inequalidade do domínio da gama de possibilidades é permitida, i. e. "y < z", "y ≤ z", "w < y < z", "w < y ≤ z", "w ≤ y < z", "w ≤ y ≤ z". "Quando a gama de possibilidaddes não contém y tal que R(y) [é "verdade"], o valor da expressão "μy" é o número cardinal da gama de possibilidades"(p. 226); esta é a razão pela qual o "z" padrão aparece na definição acima. Como mostrado abaixo, o operador mu "μy_y<z" é definido em termos de duas funções recursivas primitivas chamadas a finita Σ e produto finito Π, uma função predicado que "faz oi teste" e uma função indicadora que converte { t, f } para { 0, 1 }.

No capítulo XI §57 General Recursive Functions, Kleene define o operador-μ sobre a variável y da seguinte maneira,

"$(\exists y)\mu yR(y)=\{{\mbox{o mínimo (número natural)}}\ y\ {\mbox{tal que}}\ R(y)\}$" (p. 279, onde "$(\exists y)$" significa "Existe um y tal que..."

Nessa mesma instancia R, ou sua função indicadora, retorna 0 quando é satisfeita (i.e. retorna verdadeiro); a função então retorna o número y. Nenhum limite superior existe em y, tal que nenhuma expressão de desigualdade aparece na sua definição.

Par uma dada R(y) o operador mu ilimitado μyR(y) (perceba nenhum requerimento para "(Ey)" ) é uma função parcial. Kleene a faz como uma função total, contrariamente (cf. p. 317):

εyR(x, y) =

• o mínimo y tal que R(x,y) [é verdadeiro], se (Ey)R(x,y)
• 0, caso contrário.

Propriedades

(i) No contexto de funções recursivas primitivas, onde a variável de busca y do operador-µ é limitado, e.g. y<z na fórmula abaixo, se o predicado R é primitivo recursivo (Kleene Proof #E p. 228), então

μy_y<z R( y, x₁,..., x_n ) is a função recursiva primitiva.

(ii) No contexto de (total) funções recursivas: Onde a variavel de busca y é ilimitada mas tem garantia de existir para todo valor x_i dos parametros do predicado recursivo total R, :(x₁), ..., (x_n) (Ey) R( y, x_i, ... x_n ) implica que μyR(y, x_i, ... x_n) é uma função recursiva total.

aqui (x_i) significa "para todo x_i" e Ey significa "existe pelo menos um valor de y tal que..." (cf Kleene (1952) p. 279.)

então os cinco operadores recursivos primitivos mais o ilimitado-mas-total operador-µ da margem ao que Kleene chamou de funções recursivas "genéricas" (i.e. funções totais definidas pelos seis operadores recursivos).

(iii) No contexto de funções recursivas parciais: Suponha que a relação R tem se e somente se uma função recursiva parcial converja a zero. E suponha que tal função recursiva parcial converja (para algo, não necessariamente zero) sempre que $\mu yR(y,x_{1},\ldots ,x_{k})$ is defined and y is $\mu yR(y,x_{1},\ldots ,x_{k})$ ou menor. Então a função $\mu yR(y,x_{1},\ldots ,x_{k})$ é também uma função recursiva parcial.

O operador µ é usado na caracterização de funções computáveis tais quais funções recursivas µ.

Em matemática construtíva, o operador de busca ilimitado é associado ao princípio de Markov.

Exemplos

Exemplo #1: O operador-µ limitado é uma função recursiva primitiva

A seguir, para economizar espaço a fonte negrito x i.e. x representará a string x_i, . . ., x_n.

O operador-µ limitado pode ser expresso de maneira um tanto simples em termos de duas funções recursivas primitivas (hereafter "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 page 224). (Como necessitado, qualquer limite para a variável tal que s≤t ou t<z, ou 5<x<17 etc. é apropriado). Por exemplo:

• Π_s≤t f_s (x, s) = f₀(x, 0) * f₁(x, 1) * . . . * f_t(x, t)
• Σ_t<z g_t ( x, t ) = g₀( x, 0 ) + g₁(x, 1 ) + . . . + g_z-1(x, z-1 )

Antes de procedermos temos que introduzir a função ψ chamada "a função indicadora" do predicado R. Função ψ é definida de entradas ( v="verdade", f="falsidade" ) para saidas ( 0, 1 ) (Observe a ordem!). Neste caso a entrada para ψ i.e. { v, f } é vinda da saida de R:

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

Kleene demonstra que μy_y<z R(y) é definida como a seguir; vemos que a função produto Π está agindo como um operador booleano OR, e a soma Σ está agindo de alguma maneira como a função booleana AND mas está produzindo { Σ≠0, Σ=0 } ao invés de somente { 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 ) ]

Σ é na verdade uma recursão primitiva com a base Σ(x, 0) = 0 e o passo de indução Σ(x, y+1 ) = Σ( x, y ) + Π( x, y ). O produto Π é também uma recursão primitiva Π com passo base Π( x, 0 ) = ψ( x, 0 ) e passo de indução Π( x, y+1 ) = Π( x, y )*ψ( x, y+1 ).

A equação é mais facilmente observada com um exemplo, como fornecido por Kleene. Ele apenas inventou as entradas para a função indicadora ψ(R(y)). Ele designou as funções representativas χ(y) ao invés 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
mínimo y<z tal que R(y) é "verdade": φ(y) = μy y<z R(y)				3

Exemplo #2: O operador-µ ilimitado não é primitivo-recursivo

O operador µ ilimitado-a função µy─é a usualmente definida em textos. Mas o leitor pode se perguntar porque-os textos modernos não definem a razão─o operador-µ ilimitado procura pela função R(x, y) para devolver zero, ao invés de algum outro número natural.

Em uma nota de rodapé Minsky permite que seu operador pare quando a função interna produzir uma correspondencia ao 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 µy vai ser definido em termos da função "produto" Π com seu índice y podendo "crescer" ao passo que o operador µ procura. Como observado no exemplo acima, o produto Π _x<y de uma string de números ψ(x, 0) *, . . ., * ψ(x, y) resulta em zero quando qualquer um dos termos ψ(x, i) é zero:

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

se qualquer ψ(x, i)=0 onde 0 ≤ i ≤ s. Entretanto Π age como um AND booleano.

A função µy produz como "saída" um único número natural y = { 0, 1, 2, 3 ... }. Contudo, dentro do operador uma de algumas "situações" pode ocorrer: (a) uma "função de número teórica" χ que produz um número natural único, ou (b) um "predicado" R que produz tanto { v= verdadeiro, f = falso }. (E, no contexto de funções recursivas parciais Kleene mais tarde admite um terceiro resultado: "µ = indecidível", pp. 332ff).

Kleene divide sua definição de operador µ ilimitado para entregar as duas situações (a) e (b). Para a situação (b), antes do predicado R(x, y) poder servir em uma capacidade aritmética na produção Π, sua saída { v, f } tem que primeiro ser "operada" pela sua função indicadora χ para devolver { 0, 1 }. E para a situação (a) se uma definição deve ser usada então a função numérica teórica χ tem que produzir zero afim de satisfazer o operador µ. Com esse propósito definido, ele demonstra com "Prova III" única que tanto tipos (a) ou (b) juntos com os cinco operadores recursivos primitivos devolvem as (total) funções recursivas ... com esta circunstancia para a função total:

Que para todos os parametros x, uma demonstração que deve ser provida para mostrar que um y existe tal que satisfaz (a) µy ψ(x, y) ou (b) R(x,y).

Kleene também admite uma terceira situação (c) que não querer a demonstração de "para todo x um y existe tal que ψ(x, y)." Ele utiliza esta na sua prova de que mais funções recursivas totais existem do que podem ser enumeradas.

A prova de Kleene é informal e usa um exemplo similar ao do primeiro exemplo. Mas primeiro ele invoca o operador-µ à uma forma diferente que usa o "produto-de-termos" Π operando na função χ que devolve um número natural n conde n pode ser qualquer número natural, e 0 na instancia quando o teste do operador µ é "satisfeito".

A definição reinvoca 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 ) é indefinida para u = 0 or v > 0.

Isto é sutil. A primeira vista as equações parecem usar recursão primitiva. Mas Kleene não nos proveu o passo base e o passo de indução da forma geral:

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

O que houve? Primeiro, temos que nos lembrar de que designamos um parâmetro (um número natural) para cada variavel x_i. Segundo, vemos um operador-sucessor trabalhando iterando y (e.g. y'). E terceiro, vemos que a função µy _y<zχ(y, x) está apenas produzindo instancias de χ(y,x) i.e. χ(0,x), χ(1,x), ... até que uma instancia pare e devolva 0. Quarto, quando uma instancia χ(n,x) para e devolve 0 isto faz com que o termo médio de τ, i.e. v = π( x, y' ) pare e devolva 0. Finalmente, quando o termo médio v = 0, µy _y<zχ(y) executa a linha (iii) e "sai". A apresentação de equações de Kleene (ii) e (iii) foram trocadas para mostrar a idéia de que a linha (iii) representa uma saída─uma saída usada somente quando a busca encontra com sucesso um y que satisfaz χ(y) e o termo-produto π(x, y' ) é 1; o operador então para sua busca com τ(z', 0, y) = y.

τ( π(x, y), π( x, y' ), y), i.e.:

• τ( π(x, 0), π( x, 1 ), 0),
• τ( π(x, 1), π( x, 2 ), 1)
• τ( π(x, 2), π( x, 3 ), 2)
• τ( π(x, 3), π( x, 4 ), 3)
• . . . . . até que uma correspondencia ocorra em y=n e então:
• τ(z', 0, y) = τ(z', 0, n) = n e a busca do operador μ for feita.

Para o exemplo Kleene "...considera(am)-se quaisquer valores fixos de x_i, ... x_n) e escreve(m) 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	. . .
				↑
mínimo y<z tal que R(y) é "verdade": φ(y) = μy y<z R(y)				3

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

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

A demonstração a seguir segue Minsky sem "a peculiaridade" mencionada na nota de rodapé. A demonstração usará uma modelo de contra-máquina "sucessora" bastante relativa aos Axiomas de Peano e as funções recursivas primitivas. O modelo consiste em (i) uma máquina de estado finita com uma tabela de instruções e o chamado 'registrador de estado' que vamos renomear para "o Registrador de Instruções" (IR), (ii) alguns "registradores" tais quais podem conter apenas um número singular natural, e (iii) um set de instruções de quatro "commandos" descritos na tabela a seguir:

A seguir, o símbolo " [ r ] " significa "o conteúdo de", e " →r " indica uma ação com respeito ao registrador r.

Instrução	Mnemonico	Ação em registrador(es) "r"	Ação no Registrador de Instruções, IR
Limpar registrador	CLR ( r )	0 → r	[ IR ] +1 → IR
INCrementar registrador	INC ( r )	[ r ] +1 → r	[ IR ] +1 → IR
Pule se Igual	JE (r1, r2, z)	none	IF [ r1 ] = [ r2 ] THEN z → IR ELSE [ IR ] +1 → IR
Parar (Halt)	H	none	[ IR ] → IR

O algoritmo para o operador de minimização μy [φ( x, y )] vai, em essência, criar uma sequencia de instancias da função φ( x, y ) enquanto o valor do parametro y (um número natural) aumenta; o processo vai continuar (veja Nota † abaixo) até que uma correspondencia entre as saidas da função φ( x, y ) e um número pre-estabelecido (normalmente 0). Então a avaliação de φ(x, y) requer, registrador "w", e um número (normalmente 0) para registrar y.

Nota †: O operador µ ilimitado vai continuar esse processo de tentativa-de-correspondencia ad infinitum ou até que uma correspondencia ocorra. Então o registrador "y" tem que ser ilimitado - ele deve ser capaz de "aguentar" um número de tamanho arbitrário. Diferentemente de um modelo computacional "real", modelos de máquinas abstratas permitem isto. No caso de um operador µ limitado, um operador µ de limite inferior começaria com o conteúdo de y aplicado a um número diferente de zero. Um operador µ de limite superior requeriria um registrador adicional "ub" para conter o número que representa o limite superior. mais uma operação de comparação adicional; um algoritmo pode pode prover para limites tanto superior quanto inferior.

A seguir assumimos que o Registrador de Instruções (IR) encontra a rotina µy no número de instrução "n". Sua primiera ação vai ser de estabelecer um número em um dado registrador "w"─um exemplo do número que a função φ( x, y ) deve produzir antes de o algoritmo poder terminar (à maneira clássica este é o número 0, mas veja a nota de rodapé sobre números diferentes de 0). A próxima ação do algoritmo na instrução n+1 vai ser de limpar o registrador "y" -- "y" vai agir como um eixo que começa com 0. Então na instrução n+2 o algoritmo avalia sua função φ( x, y ) -- assumimos que isso leva j instruções para completar─e no fim desta avaliação φ( x, y ) deposita sua saída no registrador "φ". Na instrução n+j o algoritmo compara o número no registrador "w" (e.g. 0) ao número no registrador "φ"─se eles são o mesmo o algoritmo obteve sucesso e escapa pela saída; caso contrário incrementa o conteúdo do registrador "y" e itera de volta com seu novo valor-y para testar a função φ( x, y ) novamente.

IR		Instrução	Ação em registrador	Ação no Registrador de Instruções, IR
n	μy[ φ( x, y ) ]:	CLR ( w )	0 → w	[ IR ] +1 → IR
n+1		CLR ( y )	0 → y	[ IR ] +1 → IR
n+2	loop:	φ ( x, y )	φ( [x], [y] ) → φ	[ IR ] +j+1 → IR
n+j+3		JE (φ, w, exit)	none	CASE: { IF [φ]=[w] THEN exit → IR ELSE [IR] +1 → IR }
n+j+4		INC ( y )	[ y ] +1 → y	[ IR ] +1 → IR
n+j+5		JE (0, 0, loop)	Pulo incondicional	CASE: { IF [r0] =[r0] THEN loop → IR ELSE loop → IR }
n+j+6	exit:	etc.

Notas de rodapé

Demonstração de função total

O que é mandatório se a função é uma função total é uma demonstração por algum outro método (e.g. indução) que para cada combinação de valores de seus parâmetros x_i algum número natural y vai satisfazer o operador-µ de maneira que o algoritmo que representa o cálculo poderá terminar:

"... nós devemos sempre hesitar em assumir que um sistema de equações realmente define uma função recursiva genérica [i.e. total].e.g. na forma de uma prova por indução que, para cada valor de argumento, a computação termina com um único valor." (Minsky (1967) p. 186)

"Em outras palavras, não devemos afirmar que uma função é calculável efetivamente no sentido de que se mostrou ser genérica [i.e. total] recursiva, a menos que a demonstração de que é recursiva genérica é efetiva." (Kleene (1952) p. 319)

Por exemplo do que isso significa na prática veja exemplos em funções µ recursivas─até mesmo o algoritmo mais simples ("impróprio") de subtração "x - y = d" pode significar, para casos indefinidos quando x < y, (1) não terminar, (2) nenhum número (i.e. algo errado com o formato tal que o returno não é considerado um número natural), ou (3) engano: números errados no formato correto. A o algoritmo de subtração "correto" requer bastante atenção para 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 instancias { (0, 0), (1, 0), (0, 1), (2, 1), (1, 1), (1, 2) }, somos deixados com um sentimento de insegurança até que possamos conceber uma demonstração convincente de que os casos (x, y) = (n, m) todos retornam os resultados esperados. Para a idéia de Kleene: nossa "demonstração" (i.e. o algoritmo que é nossa demonstração) é convincente o suficiente para ser considerada efetiva?

Modelos alternativos de máquinas abstratas do operador µ 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 vai retornar t = 0 quando seu predicado (o teste IF-THEN-ELSE) é satisfeito; na verdade, retorna 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 vai conter 0, mas Minsky observa que pode conter qualquer número k. O conjunto de instruções de Minsky é equivalente ao seguinte onde "JNE" = Pula para z se Não é Igual:

{ CLR (r), INC (r), JNE (r_j, r_k, z) }

IR		Instrução	Ação em registrador	Ação no Registrador de Instruções, IR
n	μy φ( x ):	CLR ( w )	0 → w	[ IR ] +1 → IR
n+1		CLR ( t )	0 → t	[ IR ] +1 → IR
n+2	loop:	φ ( 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)	none	CASE: { IF [φ] ≠ [w] THEN "exit" → IR ELSE [IR] +1 → IR }
n+j+5		INC ( t )	[ t ] +1 → t	[ IR ] +1 → IR
n+j+6	exit:	etc..

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

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

Nesta versão o contador "y" é chamado "r2", e a função f( x, r2 ) deposita seu número no registrador "r3". Talvez a razão pela qual Boolos-Burgess-Jeffrey limpa r3 é para facilitar um pulo incondicional para loop; isto é comumente feito por uso de um registrador dedicado "0" que contém 0".

IR	Instrução	Ação em registrador	Ação no Registrador de Instruções, IR
n	μr2[f(x, r2)]:	CLR ( r2 )	0 → r2	[ IR ] +1 → IR
n+1	loop:	f( y, x )	f( [ t ], [ x ] ) →r3	[ IR ] +j+1 → IR
n+2		JZ ( r3, exit )	none	IF [ r3 ] = 0 THEN exit → IR ELSE [ IR ] +1 → IR
n+j+3		CLR ( r3 )	0 → r3	[ IR ] +1 → IR
n+j+4		INC ( r2 )	[ r2 ] +1 → r2	[ IR ] +1 → IR
n+j+5		JZ ( r3, loop)		CASE: { IF [ r3 ] =0 THEN loop → IR ELSE [IR] +1 → IR }
n+j+6	exit:	etc..

Referências

• Stephen Kleene (1952) Introduction to Metamathematics, North-Holland Publishing Company, New York, 11th reprint 1971: (2nd edition notes added on 6th reprint).
• Marvin L. Minsky (1967), Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.

  Nas páginas 210-215 Minsky mostra como criar o operador μ usando o modelo register machine, demonstrando assim a sua equivalência às funções recursivas gerais.

• George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70–71.