Decidibilidade da existência invariante indutiva na aritmética de Presburger

Problema:

Considere um número finito de estados de controle (incluindo um estado "inicial" e "ruim"), um número finito de variáveis inteiras e, para cada par de estados ordenados, uma relação de transição expressa na aritmética de Presburger.

Decida se existe um invariante indutivo (= estável pelos pós-estados da relação de transição) contendo o estado inicial, mas não o mau, definível na aritmética de Presburger.

(Observe que esse problema é diferente do problema de alcançabilidade na aritmética Presburger, que é claramente indecidível (por redução em máquinas com dois contadores).)

Suspeito que esse problema seja indecidível, mas não conheço nenhuma prova disso. (É obviamente semidecidável.) Alguém já provou isso?

lo.logic pl.programming-languages decidability David Monniaux
fonte

Eu penso que é preciso esclarecer este um pouco: os estados são representados por um número inteiro

, e a relação de transição é uma fórmula

, com uma fórmula

que representam os estados iniciais e os estados ruins, respectivamente? E você está procurando uma fórmula

tal que:

n, m

$n, m$

ϕ (n, m)

$\phi(n,m)$

ψ_{g o o d} (n)

$\psi_{\mathrm{good}}(n)$

ψ_{b a d} (n)

$\psi_{\mathrm{bad}}(n)$

I (n)

$I(n)$

. Isso está correto?

I (n) \land ϕ (n, m) \to I (m)

$I(n)\wedge\phi(n,m) \rightarrow I(m)$

ψ_{g o o d} (n) \to I (n)

$\psi_{\mathrm{good}}(n) \rightarrow I(n)$

ψ_{b a d} (n) \to \neg I (n)

$\psi_{\mathrm{bad}}(n) \rightarrow \neg I(n)$

Cody

Sim, excepto que

não são inteiros individuais, mas finitas vectores de números inteiros de dimensão fixa

( "número finito de variáveis inteiras"). Obrigado pelo esclarecimento.

n

$n$

m

$m$

d

$d$

David Monniaux

Então, qual é o problema de acessibilidade? Se é apenas "o estado

é alcançável", então é fácil mostrar que os problemas são equivalentes: se

está inacessível, tome

para ser

ψ_{b a d} (k)

$\psi_{\mathrm{bad}}(k)$

ψ_{b a d} (k)

$\psi_{\mathrm{bad}}(k)$

I (k)

$I(k)$

. Estou esquecendo de algo?

ψ_{g o o d} (k) \lor (\forall y, ϕ (y, k) \land \neg ψ_{b a d} (y) \to \neg ψ_{b a d} (k))

$\psi_{\mathrm{good}}(k)\vee(\forall y, \phi(y,k)\wedge\neg\psi_{\mathrm{bad}}(y)\rightarrow \neg\psi_{\mathrm{bad}}(k))$

Cody

Desculpe, 1) é

2) por que o seu conjunto seja indutiva? por exemplo, por que

I (n) \to ψ_{bad} (n)

$I(n) \rightarrow \psi_{\textrm{bad}}(n)$

ψ_{good} (k) \land ϕ (k, k^{'}) \to I (k^{'})

$\psi_{\textrm{good}}(k) \land \phi(k,k') \rightarrow I(k')$

David Monniaux

O problema indutivo do separador invariante da aritmética de Presburger é indecidível.

Não conheço uma prova na literatura para apontá-lo. (Parece uma pergunta tão direta que suponho que esteja em algum lugar por aí.) A prova que me veio a seguir segue aproximadamente a mesma construção que o problema da parada. Aqui está uma breve visão geral. Em primeiro lugar, assumir um procedimento de decisão existe e, em seguida, construir uma máquina de com entrada . usa para decidir a não terminação de em si mesmo e, em seguida, reverte a saída. Em seguida, usamos a construção de para mostrar que deve dar uma resposta incorreta sobre a execução de em si. $D$ $S$ $M$ $S$ $D$ $M$ $S$ $S$ $D$ $S$

Em vez de uma redução no problema de parada, a prova é para todos os efeitos e uma reafirmação da prova do problema de parada. É um pouco detalhado, pois exigirá que a condição exata mais forte possa ser expressa. (Se uma prova mais simples for possível, eu estaria muito interessado em ouvi-la.) Agora, vamos aos detalhes sangrentos.

O problema separador invariante indutivo para Presburger aritmética é para um determinado 4-tupla onde é um conjunto finito de nomes de variáveis, e são fórmulas de Presburger cujas variáveis livres estão em , é a fórmula de Presburger cujas variáveis livres estão em ou $\left<\bar v,Init,Next, Bad\right>$ $\bar v$ $Init$ $Bad$ $\bar v$ $Next$ $\bar v$ (uma cópia inicial de ) existe uma fórmulana aritmética de Presburger com variáveis livres em modo que: $\bar{v}'$ $\bar v$ $\phi$ $\bar v$

$Init \implies \phi$
$\phi \land Next \implies \phi'$
$\phi \implies \lnot Bad$

onde inicia todas as variáveis livres em . $\phi'$ $\phi$

Suponha que esse problema seja decidível. Existe então uma máquina de Turing que decide o problema do separador (para uma determinada codificação de fórmulas de Presburger). Seja uma máquina de Turing determinística que simula . termina e decide o problema do separador. $D'$ $D$ $D'$ $D$

Uma atribuição variável ao longo de um conjunto finito de variáveis representa um conjunto onde é um número inteiro constante. $\{v_i\}$ $\bigwedge v_i = c_i$ $c_i$

Também assumirei a existência de uma máquina de Turing para o compilador aritmético Presburger com algumas restrições razoáveis, mas fortes. toma como entrada de uma máquina de Turing com um único estado final, e uma entrada , e construções Presburger fórmulas e ao longo de um conjunto finito de variáveis . Informalmente, exigimos que os caminhos das fórmulas de Presburger simulem a execução de em $C$ $C$ $M$ $term$ $w$ $Init$ $Next$ $\bar v$ $M$ $w$ . Além disso, exigimos que seja uma simulação de etapas. Formalmente, exigimos que:

designa uma única constante para todos os estados de controlo em e deixar a constante de ser , $C$ $M$ $term$ $\left<term\right>$
inclui uma variável in que rastreia o estado de controle de a cada passo da execução, $C$ $pc$ $\bar v$ $M$
gera de estar sob a forma de uma atribuição variável ao longo , $C$ $Init$ $\bar v$
assegura que tenha um sucessor único em atribuições variáveis acima de (que são alcançáveis de ) se for determinístico, $C$ $Next$ $\bar v$ $Init$ $M$
para que exista uma função injetiva de um estado de (controle e fita) para uma atribuição de variável sobre modo que tenha um sucessor, o estado inicial de em é mapeado para exatamente e o estado de controle atribui consistentemente , $f$ $M$ $bar v$ $Next$ $M$ $w$ $Init$ $M$ $pc$
é determinístico e $C$
termina. $C$

Agora construa a máquina de Turing que usa uma máquina de Turing como entrada e faça o seguinte (em pseudocódigo): $S$ $M$

S(M):
   Run C(M,M) to get v, Init and Next
   Simulate D on v, Init, Next, Bad := (pc = <term>)
   If D says a separator exists:
     terminate
   If D says no separator exists:
     loop: goto loop

$D$ $S$ $S$ $S(S)$ $C$ $Init$ $Next$ $S$ $S$ $i$ $S(S)$ $s_i$ $i$ $\bar v_i = f(s_i)$ $Next$ $Init$ $S$ $C$ $Next$ $Init$ $f(s_0)=\bar v_i=Init$

$D$ $\phi$ $S(S)$ $term$ $k$ $C$ $D$ $\bar v_1 \ldots \bar v_k$ $\phi$ $pc = \left<term\right>$ $D$

$D$ $S(S)$ $loop$ $k$ $k$ $s_{k+1}=s_{k+2}=\ldots$ $k$ $\phi = \bigvee_{i=1}^{k+1} \bar v_i$ $\phi$ $Next$ $Init$

$Init \implies \phi$ $Init$ $\bar v_1$
$\phi \land Next \implies \phi'$ $Next$ $i$ $\bar v_i$ $\bar v_{i+1}'$
$\phi \implies \lnot Bad$ $\bar v_i$ $pc \neq \left<term\right>$

$\phi$ $\left<\bar v,Init,Next, Bad\right>$ $D$

$D$

Realizar esse exercício realmente me fez apreciar o trabalho de Jerome Leroux em separadores para sistemas de adição de vetores.

Tim
fonte

Isso é ótimo, obrigado! Você tem uma referência para a etapa 2, a saber, o "compilador da TM para a aritmética de Presburger"? Esse parece ser o cerne da prova.

Cody

i

$i$

i^{'}

$i'$

i \leq i^{'}

$i \leq i'$

t

$t$

2^{p}

$2^p$

p

$p$

2^{p}

$2^p$

t

$t$

\exists l, c, r

$\exists l,c,r$

l \leq 2^{p}, c < 2, r \geq 2^{p + 1}

$l \leq 2^p, c < 2, r \geq 2^{p+1}$

(l + p + r = t => c = 1)

$(l + p + r = t => c=1)$

(l + r = t => c = 0)

$(l + r = t => c=0)$

Decidibilidade da existência invariante indutiva na aritmética de Presburger

Respostas: