Le mappe semantiche denotazionali sono decidibili?

Question

Mi scuso per la mia scarsa espressione di questa domanda, non sono sicuro di avere il vocabolario per chiederlo in modo appropriato.

che ho scritto (molto poco) qualcosa di simile a

⟦let x = x in x⟧ = ⊥ 

ma in realtà sto riuscendo a capire qualcosa di complicato qui. Posso affermare che questa affermazione è veramente ⊥ perché so che è un ciclo infinito non produttivo. Inoltre, posso affermare qualcosa di simile

⟦let ones = 1:ones in ones⟧ = μ(λx.(1,x)) = (1, (1, (1, ...))) 

ma ciò che accade in quel elipsis? Presumibilmente è un numero infinito di "1-and-tuples", un oggetto matematico perfettamente definito se stai bene con l'AFA, ma come posso convincerti che non è un numero finito di "1-and-tuples"? e quindi un non produttivo ⊥?

Ovviamente, ciò comporta rispondere al problema della terminazione, quindi non posso in generale.

Quindi, in questo caso, come possiamo calcolare mapping semantici come se fossero una funzione totale? La semantica è necessariamente non deterministica per le lingue incomplete di Turing? Immagino che significhi che la semantica sia sempre e solo una descrizione approssimativa e informale di una lingua, ma questo "buco" va oltre?

Answer 1

ci sono modelli teorici serie di Turing lingue complete. Se la tua lingua è fortemente normalizzata, esci da una funzione totale per "interpretarla" su qualcosa. Si può o non si può avere una semantica teorica in una lingua completa non turante. Indipendentemente dal fatto che le lingue siano complete e non complete, le lingue possono avere semantica teorica non impostata con funzioni di mappatura semantica totale.

non credo che sia il problema qui.

C'è una differenza tra le definizioni induttive e co-induttivo. Possiamo esplorare questo insieme teoricamente:

La definizione induttiva di una lista di interi legge:

il set [Z] è la più piccolo set S in modo tale che la lista vuota è in S, e tale che per qualsiasi ls in S e n in Z coppia (n,ls) in S.

Questo può anche essere presentato in un modo "step indicizzato", come [Z](0) = {[]} e [Z](n) = {(n,ls) | n \in Z, ls \in [Z](n-1)} che consente di definire [Z] = \Union_{i \in N}([Z](n) (se si crede in numeri naturali!)

D'altra parte, "liste" in Haskell sono più strettamente correlate a "flussi coinduttive" che sono definiti coinductively

set [Z] (coinduttiva) è la più grande impostato S tale che forall x in S, x = [] o x = (n,ls) con n in Z e ls in S.

Cioè, le definizioni coinduttive sono al contrario. Mentre le definizioni induttive definiscono il set più piccolo contenente alcuni elementi, le definizioni coinduttive definiscono l'insieme più grande in cui tutti gli elementi assumono una certa forma.

È facile dimostrare che tutte le liste induttive hanno una lunghezza finita, mentre alcune liste coinduttive sono infinitamente lunghe. Il tuo esempio richiede la coinduzione.

Più in generale, le definizioni induttive possono essere come il "punto di meno fissazione di un funtore" mentre le definizioni coinduttive possono essere pensate come "il più grande punto fisso di un funtore". Il "minimo punto fisso" di un functor è proprio la sua "algebra iniziale" mentre il "punto di massima fissazione" è il suo "coalgebra finale". Usando questo come strumenti semantici è più facile definire le cose in categorie diverse dalla categoria di insiemi.

trovo che Haskell fornisce un buon linguaggio per descrivere questi funtori

data ListGenerator a r = Cons a r | Nil 

instance Functor (ListGenerator a) where 
    fmap f (Cons a x) = Cons a (f x) 
    fmap _ Nil  = Nil 

anche se Haskell fornisce un buon linguaggio per descrivere questi funtori, in quanto la sua funzione di spazio è CBN e la lingua non è totale, non abbiamo modo di definire il tipo di minimo punto fisso vorremmo :(, anche se facciamo ottenere la definizione del più grande punto fisso

data GF f = GF (f (GF f)) 

o la non ricorsivo esistenzialmente quantificata

data GF f = forall r. GF r (r -> (f r)) 

se stavamo lavorando in un linguaggio rigoroso o totale, il minimo punto fisso sarebbe l'universalmente quantificati

data LF f = LF (forall r. (f r -> r) -> r) 

EDIT: dal più "piccolo" è un insieme nozione teorica se il "minimo" /" la più grande "distinzione potrebbe non essere quella giusta. La definizione di LF è sostanzialmente isomorfa a GF ed è "l'algebra iniziale gratuita" che è il formalismo categorico di "punto di correzione minimo".

da

come posso convincerlo che non è un numero finito di "1-e-tuple" e quindi un non-produttiva ⊥?

non si può a meno che non credo nel tipo di costruzioni in questo post. Se lo faccio, allora la tua definizione mi lascia bloccato !. Se dici "ones è il flusso coinduttivo composto dalla coppia (1,ones)" allora devo crederci! So che ones non è _|_ per definizione, e quindi per induzione posso dimostrare che non può essere il caso che per qualsiasi valore n ho n e poi in basso. Posso provare a negare che la tua affermazione stia solo negando l'esistenza di vapori coinduttivi.

Answer 2

Per ulteriori sulle tecniche di prova più di strutture coinduttive (in espansione sulla risposta molto bella di Filippo JF), si può dare un'occhiata a Hinze e James' 'provare l'unico punto fisso-principio corretto': http://www.cs.ox.ac.uk/people/daniel.james/unique/unique-tech.pdf