Turing-completezza linguaggi logici

Messaggioda Dirk_Pitt » 12/01/2012, 19:54

Buonasera, vorrei avere spiegazioni sulla seguente questione: la definizione di turing-completezza cosa significa per un linguaggio logico? In base a ciò, come verificare (ad esempio) che il linguaggio del primo ordine è turing-completo? Oppure che lo è la default logic in cui si possano usare anche le funzioni?

Grazie, ciao!
Dirk_Pitt
Starting Member
Starting Member
 
Messaggio: 1 di 19
Iscritto il: 01/05/2008, 22:53

Re: Turing-completezza linguaggi logici

Messaggioda Deckard » 13/01/2012, 00:20

Non ho mai sentito parlare esattamente di turing-completezza della logica del primo ordine. Questo per il semplice fatto che non viene definita una nozione di computabilità. Ciò invece a cui si fa riferimento in un linguaggio logico è la rappresentabilità di una funzione in una teoria.
Senza sottilizzare sulle nozioni formali, che puoi trovare tu stesso in un qualsiasi manuale di logica, una funzione si dice rappresentabile in una teoria $T$ sse se $f(k_1, ... , k_n) = k$ allora esiste una formula $A(x_1, ... , x_n, y)$ t.c. è dimostrabile in $T$ che $AAy( A(bar(k_1), ... , bar(k_n),y) harr y=bar(k))$ dove $bar(k)$ indica il "nome" del numero $k$.
Un concetto equivalente alla turing-completezza per un linguaggio logico può essere quindi considerata la rappresentabilità delle funzioni ricorsive (che sono le stesse calcolabili da una macchina di Turing) all'interno di una teoria in tale linguaggio.
Ad es. la teoria dell'aritmetica di Peano (PA) nel linguaggio di primo ordine permette di rappresentare tutte le funzioni ricorsive.
Un piccolo accenno sul come dimostrare questo fatto: la classe delle funzioni ricorsiva è la più piccola classe di funzioni che contiene determinate funzioni iniziali e che è chiusa per alcune operazioni; è quindi sufficiente mostrare, per induzione, che in PA è possibile rappresentare le funzioni iniziali e le funzioni ottenute applicando quelle operazioni a funzioni ricorsive.
Spero di averti dato almeno un'idea.
http://www.mathcomp.leeds.ac.uk/turing2012/

Hilbert space is a big place.
Deckard
Junior Member
Junior Member
 
Messaggio: 239 di 293
Iscritto il: 17/08/2010, 09:58

Re: Turing-completezza linguaggi logici

Messaggioda Dirk_Pitt » 13/01/2012, 01:25

Intanto grazie per la risposta :) A mio parere la calcolabilità di un linguaggio logico è da analizzarsi in relazione alla sua espressività (benchè io sappia che lesiano cose diverse a rigore). Ad es, il SAT in logica proposizionale è NP-compl, il ''SAT'' al prim'ordine è RE (ma non R, a causa dei simboli di funzione). Trovare un estensione per una teoria logica di default è un probl sigmaP2-compl.

Cosa ne pensi se io dicessi che un linguaggio logico L è turing-compl se esiste una riduzione dal linguaggio universale ad L? (non l ho letto da nessuna parte, è solo una mia idea).

Inoltre vorrei chiederti chiarimenti su questo: a lezione il prof ha detto che la logica del prim'ordine è completa perchè possiamo associare i simboli di costante ai simboli sul nastro di una macchina di T, i predicati agli stati della macchina, e i funtori al nastro della macchina stessa. A me questo ragionamento, benchè sia comprensibile, risulta un pò oscuro.

Grazie, ciao!
Dirk_Pitt
Starting Member
Starting Member
 
Messaggio: 2 di 19
Iscritto il: 01/05/2008, 22:53

Re: Turing-completezza linguaggi logici

Messaggioda Deckard » 13/01/2012, 10:43

Cosa ne pensi se io dicessi che un linguaggio logico L è turing-compl se esiste una riduzione dal linguaggio universale ad L? (non l ho letto da nessuna parte, è solo una mia idea).

Informalmente potrebbe anche andare bene, però formalmente credo tu stia mischiando due cose ben diverse: un conto sono i problemi di decisione, come SAT, a cui viene associato un linguaggio, il linguaggio delle parole accettate. Con il linguaggio del primo ordine non puoi fare lo stesso ragionamento, non hai la nozione di "parola accettata". Quello su cui puoi ragionare è sì il livello di espressibilità, ma è proprio per questo che s'introduce la rappresentabilità. Perché il mondo delle mdT e il mondo del linguaggio di primo ordine sono alla fine uno lo specchio dell'altro, hanno la stessa "espressività", però allo stesso tempo sono due mondi differenti: una mdT calcola una funzione, il linguaggio del primo ordine al massimo può rappresentare una funzione.

a lezione il prof ha detto che la logica del prim'ordine è completa perchè possiamo associare i simboli di costante ai simboli sul nastro di una macchina di T, i predicati agli stati della macchina, e i funtori al nastro della macchina stessa. A me questo ragionamento, benchè sia comprensibile, risulta un pò oscuro.

Mah, detto così non lo capisco neanche io :D Può anche darsi che sviluppandolo si riesca ad ottenere un ragionamento che abbia senso, però detto così sinceramente non ti so dire nulla visto che è un argomento solo abbozzato.
http://www.mathcomp.leeds.ac.uk/turing2012/

Hilbert space is a big place.
Deckard
Junior Member
Junior Member
 
Messaggio: 240 di 293
Iscritto il: 17/08/2010, 09:58

Re: Turing-completezza linguaggi logici

Messaggioda Dirk_Pitt » 13/01/2012, 15:37

Si è poco chiaro, chiederò a lui.

Approffitto della tua pazienza per chiederti qui una cosa diversa, anche se dovrei aprire un altra discussione: quando si parla di entailment classico ci si riferisce alla determinazione di un assegnamento valido per le variabili in una formula proposizionale CNF (ovvero SAT)? Inoltre se assumiamo che le clausole abbiano un numero massimo fissato di letterali questo come influisce sulla complessità del problema?

Grazie ancora :)
Dirk_Pitt
Starting Member
Starting Member
 
Messaggio: 3 di 19
Iscritto il: 01/05/2008, 22:53

Re: Turing-completezza linguaggi logici

Messaggioda Deckard » 13/01/2012, 16:03

Dirk_Pitt ha scritto:Approffitto della tua pazienza per chiederti qui una cosa diversa, anche se dovrei aprire un altra discussione: quando si parla di entailment classico ci si riferisce alla determinazione di un assegnamento valido per le variabili in una formula proposizionale CNF (ovvero SAT)?

Sinceramente non lo so. Io "entailment" l'ho sempre sentito usare per la nozione di conseguenza logica.

Dirk_Pitt ha scritto:Inoltre se assumiamo che le clausole abbiano un numero massimo fissato di letterali questo come influisce sulla complessità del problema?

Stai parlando di SAT? Se sì è facile dimostrare che il problema di decidere la soddisfacibilità di formule con clausole di al più tre elementi (3SAT) è ancora NP-completo. 2SAT invece è risolvibile in tempo polinomiale.
http://www.mathcomp.leeds.ac.uk/turing2012/

Hilbert space is a big place.
Deckard
Junior Member
Junior Member
 
Messaggio: 241 di 293
Iscritto il: 17/08/2010, 09:58

Re: Turing-completezza linguaggi logici

Messaggioda Dirk_Pitt » 13/01/2012, 16:33

Sinceramente non lo so. Io "entailment" l'ho sempre sentito usare per la nozione di conseguenza logica

Eh, appunto, pure io :)
Stai parlando di SAT? Se sì è facile dimostrare che il problema di decidere la soddisfacibilità di formule con clausole di al più tre elementi (3SAT) è ancora NP-completo. 2SAT invece è risolvibile in tempo polinomiale.


No, scusa ho scritto in modo confuso; mi riferivo all'entailment. Non capisco in che modo fissare il numero di letterali per clausola incida sulla complessità, o meglio, lo capisco ma in ogni caso la complessità deve dipendere anche dal numero di clausole, e non solo dalla loro lunghezza, o sbaglio?.
In ogni caso, se applico la risoluzione a due clausole di n ed m letterali, quante clausole si generano al max? Dato che si genera una clausola per ogni coppia di letterali complementari, e il numero di tali coppie è al massimo min(n,m) direi che è proprio questo il numero cercato. È corretto?
Dirk_Pitt
Starting Member
Starting Member
 
Messaggio: 4 di 19
Iscritto il: 01/05/2008, 22:53

Re: Turing-completezza linguaggi logici

Messaggioda Dirk_Pitt » 13/01/2012, 17:50

Segnalo questo sito che ho appena scovato:
http://pier4r.wikidot.com/learning:ai-course:4logicaproposizionale-primoordine#toc3
nella sezione ''Differenza di espressività tra logica del primo ordine e logica proposizionale'' il ragionamento c'è ma è di nuovo solo abbozzato :)
Dirk_Pitt
Starting Member
Starting Member
 
Messaggio: 5 di 19
Iscritto il: 01/05/2008, 22:53

Re: Turing-completezza linguaggi logici

Messaggioda hamming_burst » 14/01/2012, 02:14

[mini-OT]
curiosità: ma che corso universitario sarebbe dove si studiano queste argomentazioni: Computabiltiy (e famiglia) o Logica (e famiglia)?

mi pare entrambe, ma vedendo l'ulimo link proposto si parla di inferenza e dimostrazioni logiche, cosa che, almeno io, ho studiato in un corso di Semantica, ma su un modello apposito ad argomentazioni sui linguaggi; per questo la domanda :-)

[/mini-OT]
hamming_burst
Cannot live without
Cannot live without
 
Messaggio: 1569 di 4280
Iscritto il: 04/07/2009, 11:53

Re: Turing-completezza linguaggi logici

Messaggioda Deckard » 14/01/2012, 10:19

Dirk_Pitt ha scritto:No, scusa ho scritto in modo confuso; mi riferivo all'entailment. Non capisco in che modo fissare il numero di letterali per clausola incida sulla complessità, o meglio, lo capisco ma in ogni caso la complessità deve dipendere anche dal numero di clausole, e non solo dalla loro lunghezza, o sbaglio?.

Sinceramente non ho capito di cosa stai parlando. Cosa intendi per complessità in questo contesto?

In ogni caso, se applico la risoluzione a due clausole di n ed m letterali, quante clausole si generano al max? Dato che si genera una clausola per ogni coppia di letterali complementari, e il numero di tali coppie è al massimo min(n,m) direi che è proprio questo il numero cercato. È corretto?

Di nuovo, non capisco di cosa tu stia parlando. Stai utilizzando quindi il calcolo con risoluzione e fattorizzazione? Cosa intendi per letterali complementari?
Ti pregherei di spiegare un po' più precisamente ciò che chiedi. Soprattutto di definire il contesto in cui operi: è pieno di calcoli logici e varianti, condizione necessaria ma non sufficiente per risponderti è sapere di che cosa tu stia parlando.

Ad ogni modo, per ritornare un'ultima volta sulla questione di prima: quello che volevo spiegarti è che per poter affermare che ad es. il linguaggio del primo ordine è equivalente al modello della macchina di Turing è necessario introdurre la rappresentabilità delle funzioni nel linguaggio perché altrimenti come faccio a dire che il linguaggio "calcola" una funzione? Il linguaggio del primo ordine non calcola funzioni, al massimo le può rappresentare con delle formule.
http://www.mathcomp.leeds.ac.uk/turing2012/

Hilbert space is a big place.
Deckard
Junior Member
Junior Member
 
Messaggio: 242 di 293
Iscritto il: 17/08/2010, 09:58

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 8 ospiti