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, x1, . . ., xk ) é 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: "" (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 "μyy<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, "" (p. 279, onde "" 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 μyy<z R( y, x1,..., xn ) 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 xi dos parametros do predicado recursivo total R, :(x1), ..., (xn) (Ey) R( y, xi, ... xn ) implica que μyR(y, xi, ... xn) é uma função recursiva total. aqui (xi) significa "para todo xi" 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 is defined and y is ou menor. Então a função é 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 xi, . . ., xn.
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 fs (x, s) = f0(x, 0) * f1(x, 1) * . . . * ft(x, t) Σt<z gt ( x, t ) = g0( x, 0 ) + g1(x, 1 ) + . . . + gz-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 μyy<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 a fim 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 xi. 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 ideia 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 xi, ... xn) e escreve(m) simplesmente "χ(y)" para "χ(xi, ... xn),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