Wikipedia:Bar/Dimostrazione alternativa

Salve, discutendo con Utente:Moongateclimber, ho trovato una dimostrazione alternativa di un teorema di incalcolabilità. Dato che l'originale utilizza il teorema di Matyiasevich, ed è un po' ostica, ne ho elaborata una che utilizza il solo teorema di incompletezza di Gödel. Ora, teoricamente è una ricerca originale, ma essendo una dimostrazione, o è giusta o è sbagliata. Visto che della cosa si era discusso, ma non si era arrivati a nulla, e dato che la dimostrazione seguente ha anche il pregio, a mio immodesto parere, di essere chiara e semplice, ve la sottopongo per l'inserimento nell'articolo Algoritmo

Eccola qui.

Enunciato:Per ogni algoritmo, esiste un input (o uno stato di memoria) per cui questo non termina, o non dà risultati corretti

Dimostrazione. Prendiamo una macchina di Turing: essa è soggetta al TIG. Una particolarità di questo teorema è che, non appena esso è valido per un insieme di assiomi, per quanti assiomi aggiungiamo all'insieme iniziale, esso continua a valere. Dunque, carichiamo nella nostra macchina di Turing un algoritmo A, e, dato che non possiamo metterci lì ad enumerare tutti i possibili input (il nastro della macchina è infinito), aggiungiamo un bellissimo assioma a: per ogni stato iniziale i, l'algoritmo fornisce uno stato finale o.

Bene, se il TIG vale per la MdT, continua a valere per l'insieme MdT + A + a. Quindi esistono dei risultato del calcolo, palesemente derivanti dallo stato i, che il nostro insieme Mdt + A non raggiungerà mai. Ossia, esiste almeno un input per cui il programma non dimostra l'output, ossia non ci arriva: l'algoritmo non termina. Se invece decido di eliminare i cicli infiniti con qualche meccanismo (un altro assioma), allora il nostro algortimo non darà il risultato corretto. CVD.

Esempio pratico: Su una bella MdT a 6GHz nuova fiammante, col suo bel nastro infinito a corredo, implemento l'algoritmo A per cui, scritto sul nastro un numero intero positivo N, la macchian restituisce la radice quadrata del numero.

Bene, scrivo 1. La macchina di Turing a 6 GHz scrive immediatamente, con un frullio di nastro 1, e si ferma ronzante. Ottimo. Ora scriviamo 2. La nostra MdT parte in quarta e scrive 1,414213562373095.... Quando si ferma? Se vogliamo avere la radice di 2 esattta, non potrà terminare mai. Se invece vogliamo una rappresentazione che si ferma, allora quella non sarà la vera radice di due, ma un'approssimazione. Quindi ecco che appena partiti, troviamo un input il cui output, palesemente vero e corretto, non potrà mai essere raggiunto: o perché mi fermo prima, o perché ci vorrebbe un tempo infinito.

Per evitare questi limiti, serve un ipercalcolatore.

--BW Insultami 08:08, Set 23, 2005 (CEST)

Mi spiace ripetermi; la mia obiezione e' a prescindere! Torni a formulare la questione in termini di: esiste almeno un input per cui la macchina non termina! Se vai su un testo di informatica teorica, vedrai che risolvere un problema P di decisione vuol dire dare la risposta in tempo finito per un qualunque input. Se fosse vero che esiste almeno un input per cui ogni MdT non termina, nessun problema sarebbe decidibile. E ripeto: P sarebbe uguale a NP, ecc. ecc., e migliaia di teoremi di teoria della complessita' degli ultimi 20 anni sarebbero inutili. Non riesco proprio a crederci! (Tra parentesi ho visto il link sull'ipercomputing, che si dovrebbe citare nell'articolo algoritmo e qui ti do ragione, ma mi fa strano che proprio tu, sostenitore di questi nuovi modelli, mi parlassi dell'astratto della memoria infinita... mi sembra che gli ipercalcolatori siano MOLTO piu' astratti della povera buona vecchia MdT).

Ciao Moongateclimber 08:50, Set 23, 2005 (CEST)

Ciao, allora, chiariamo due cose:

non sostengo nulla. é solo la corretta e completa teoria della calcolabità: esiste l'incalcolabile, per ogni algoritmo. punto.
Non puoi obiettare a prescindere ad un teorema. Puoi dimostrare che è sbagliato.

Quindi, se il tuo testo di informatica teorica dice così, dice una corbelleria. Infatti la classe P è definita come la classe per cui la verifica delle soluzioni ha come comportamento asintotico un polinomiale. Ma non sta scritto da nessuna parte che un comportamento asintotico limite implichi che l'algoritmo di verifica termini sempre e comunque, per ogni output fornito dall'input

In caso di input o output la cui rappresentazione con numeri interi, trattati dalla MDT, sia infinita, come ad esempio i numeri reali, ecco che puoi solo calcolare un "limite" per N che tende ad infinito, e dire che il tempo è polinomiale all'INPUT. Ma essendo questo infinito, il tempo per una sua verifica è INFINITO: ossia, si vede palesemente che l'algoritmo temrminerebbe con quel risultato, ma ci vorrebbe un tempo infinito per arrivarci. Ciò non toglie che il limite di Tempo di calcolo/Grandezza dell'input esista e sia finito. --BW Insultami 08:57, Set 23, 2005 (CEST)

Mi sono letto anche la discussione, ma da quello che ho capito da qui: en:Matiyasevich's theorem e en:Recursively enumerable set ho capito che il risultato si applica solo agli insiemi ricorsivamente enumerabili rafforzandone la definizione: non solo non è garantita la terminazione, ma sappiamo che esiste almeno un input per cui l'algoritmo non termina. Ma questi casi non esauriscono l'insieme di tutti i problemi. Ad esempio, una MT in particolare può comportarsi come una macchina a stati finiti, e consideriamo la macchina che riconosce la stringa abc. Se l'inputi inizia con abc, la macchina si ferma dopo tre passi in stato "riconosciuta"; in tutti gli altri casi si ferma prima in stato "non riconosciuta". Tutti gli input successivi non contano perché la macchina è già in uno stato finale.

x Moongateclimber: la complessità (P o NP) non conta, stiamo parlando di computabilità. Ci possono essere tranquillamente problemi P semidecidibili. Banus 09:04, Set 23, 2005 (CEST)

Bene, ma considera un stringa fatta in modo che, pur avendo tutti tutti i caratteri uguali, nella rappresentazione con numeri interi, di abc, tranne le ultime, contenga proprio nelle ultime posizioni le istruzioni "resetta allo stato iniziale; ritorna all'inizio". Ecco che di nuovo l'algoritmo non termina. --BW Insultami 09:12, Set 23, 2005 (CEST)

Prima di tutto dobbiamo stabilire se stiamo parlando di MdT Universale o no. Nel secondo caso il problema non si pone perché di fatto abbiamo una macchina a stati finiti; nel primo o 1) usiamo codifiche diverse per le istruzioni e per i dati (abc) e in quel caso con l'istruzione "resetta" stiamo cambiando l'algoritmo (la macchina non riconosce più abc); oppure 2) il programma e i dati sono separati, ad esempio il programma è all'inizio, e dato il programma corretto (riconosci abc) e una qualsiasi stringa il programma termina. Banus 09:36, Set 23, 2005 (CEST)

Entrambe, ecco perché le due forme. Mi spiego meglio. Macchina di turing universale: esistono degli stati per cui il programma non termina. Automa a stati finiti: esistono dei risultati non corretti (come rappresenti l'esatta radice di due con stati finiti?). Ma mentre la seconda è banale, meno banale è la prima. Riguardo al cambiare l'algoritmo: la macchina di turing non fa distinzioni, dati, memoria e istruzioni sono la stessa cosa. E dato che ogni automa a stati finiti è rappresentabile tramite una Mdt universale, anche quello che, in particolare, adotta una codifica differente... In pratica un automa a stati finiti è una macchina di turing universale più alcuni assiomi, e quindi continua a valere il TIG. Se togliamo assiomi, allora non avremo più una Mdt. Ad esempio, se la riduco ad un flip-flop bistabile, non è più una MDT. --BW Insultami 09:48, Set 23, 2005 (CEST)

mi rendo conto della mia corbelleria su decidibilita'/complessita'. Tanto per restare a margine della discussione: la tesi di "Blakwolf" è che non esistono insiemi ricorsivi? Che non esistono problemi decidibili, ma solo semidecidibili? Tanto per capire meglio... Moongateclimber 09:45, Set 23, 2005 (CEST)

Il teorema di matyiasevich dice: in un qualunque insieme ricorsivamente enumerabile, esistono degli elementi appartenenti all'insieme non raggiungibili tramite funzioni ricorsive. é l'equivalente del TIG per le funzioni ricorsive. --BW Insultami 09:49, Set 23, 2005 (CEST)

Sì, ma esistono anche gli insiemi ricorsivi, e per quelli si ha sempre terminazione. Inoltre i TIG valgono solo per teorie abbastanza complesse da contenere l'aritmetica; in casi più semplici è possibile dimostrare la correttezza/complessità all'interno della teoria, vedi calcolo proposizionale. Banus 10:47, Set 23, 2005 (CEST)

Tratto da Insieme ricorsivo : L'insieme A è ricorsivo sse A e il suo complemento ${\bar {A}}$ sono entrambi ricorsivamente enumerabili.
Se non contiene l'aritmetica, non è una macchina di turing --BW Insultami 11:05, Set 23, 2005 (CEST)

Probabilmente questa frase, se analizzata bene, potrebbe chiarire su cos'e' che non ci stiamo capendo. Purtroppo, letteralmente, una macchina di turing contiene (non contiene) l'aritmetica non vuol dire niente. Una macchina di Turing ha una definizione insiemistica (insieme di input, insieme di output, funzioni varie) tale per cui, scegliendo l'insieme vuoto per alcuni degli insiemi in questione, ottieni un automa a stati finiti. Cioe' quindi: un automa a stati finiti e' una macchina di Turing. Ma forse ancora piu' illuminante se prendi alla lettera la tua affermazione (cioe' se consideri che un automa a stati finiti *non* e' una macchina di Turing): secondo me si ricava proprio quello che penso, e cioe' che tu per insiemi ricorsivamente enumerabili intendi gli insiemi R.E. esclusi quelli ricorsivi. Puo' essere? Anche se in tal caso il teorema di M. mi pare una tautologia...?

Gli insiemi ricorsivi, per definizione, sono ricorsivamente enumerabili. Vedi Insieme ricorsivo.
Contiene l'aritmetica significa niente altro che è possibile implementare gli assiomi dell'aritmetica con una macchina di turing. Equivalente ti suona meglio? --BW Insultami 13:49, Set 23, 2005 (CEST)

Ovvimamente perché "There is an algorithm that, when given an input eventually halts if it is a member of S" (insieme ricorsivamente enumerabile). Se sia l'insieme sia il complemento sono R.E. si può trovare facilmente un algoritmo che temina sempre con la risposta giusta: lanci entrambi e prendi il primo che si ferma.
Stiamo parlando di algoritmi, non di macchina di turing universale. Si può costruire una MdT che risponde sempre 1 dopo il primo input (con un'opportuna scelta della funzione di tramsizione di stato); è banale, non è universale ma è una MdT e un algoritmo della MdT universale. Banus 11:34, Set 23, 2005 (CEST)

No, te lo impedisce il teorema di Matyiasevich: entrambi potrebbero non terminare, in quanto entrambi contengono almeno un elemento irraggiungibile.
Certo che stiamo parlando di algoritmi. Se ovviamente fai tu il calcolo a mente, non usando una macchina di turing reale o simulata, è differente, in quanto, fino a prova contraria, noi non siamo macchine di turing. Ma la teoria degli algoritmi include la calcolabilità tramite macchine di turing universali. E dunque, per una macchina di turing, universale o a stati finiti, del genere, il teorema dice che esiste uno stato iniziale del nastro per cui non arrivi mai a stampare 1. Diverso è se quella non è una macchina di turing ma un "timbro" che stampa solo 1 e non può, neppure potenzialmente, fare altro. Se non è un timbro, è soggetta al teorema, in quanto è una macchina di Turing universale più alcuni assiomi, ed è soggetta al TIG, e dunqu al teorema dimostrato sopra. Inoltre lo stesso problema ce l'hai se usi gli assiomi dell'aritmetica (TIG), le funzioni ricorsive (Matyasevich), o un qualunque insieme di assiomi, sei sempre ingabbiato. Fortunatamente l'intuito umano va oltre ciò, altrimenti la frase di Godel non sarebbe mai stato evidentemente vera, ma indimostrabile, ma solo indimostrabile. --BW Insultami 11:54, Set 23, 2005 (CEST)

Un domanda: hai studiato informatica teorica? Il teorema è riferito agli insiemi R.E. e, se S è R.E., è sempre possibile rispondere a "n appartiene a S", ma non il contrario, (non appartenenza). Se questo vale anche per il complemento (= ricorsivo) allora almeno uno dei due algoritmi termina in tempo finito per ogni n. Nel teorema questi casi corrispondo alle eq. diofantine per cui è possibile trovare una formula (come l'ultimo teorema di Fermat).
Stai confondendo macchina di Turing con macchina di Turing universale. Una MdT può svolgere il lavoro di un automa a stati finiti, che termina sempre (se non termina si trovano automi equivalenti, stesso output per stesso input, che terminano). Prova a guardare qui. Inoltre guarda qui: che senso ha discutere della terminazione di un programma per ogni input se non è mai garantita?

Sull'automa ti rispondi da solo: se lo implementi tramite una macchina di Turing, sei soggetto al teorema di Godel. Se cambi sistema, cambi anche input critici. Vedi comunque anche nella discussione della tua pagina.--BW Insultami 09:12, Set 26, 2005 (CEST)

Sono laureato in ing. informatica e matematica. Quindi la risposta è si. Il teorema di Matyiasevich è vero, e la sua applicazione dice che
1. una macchina di turing universale è soggetta al teorema di Godel, e quindi esistono dei risultati per cui occorre un tempo infinito.
2. Se una macchina di turing è limitata, ad esempio limitando il numero di cifre, allora il teorema afferma che esiste l'instabilità numerica, ossia che per alcuni calcoli il risultato è scorretto. Il programma termina, è vero, ma in alcuni casi col risultato errato, ossia l'output vero non vine mai raggiunto.
Io non ho inventato un nuovo teorema, ne ho dato una dimostrazione col solo teorema di Godel, invece che con quello di matyiasevich, solitamente utilizzato.

Ricapitolo:

Ogni insieme ricorsivo è ricorsivamente enumerabile e soggetto al teorema di Matyiasevich.
Una macchina di turing universale è soggetta al teorema di Godel, in quanto equivalente al sistema di assiomi dell'aritmetica. Qualsiasi aggiunta di assiomi non risolve il problema, per cui esistono i casi detti sopra.
"limitare" la macchina di turing universale, cioè costruire un automa a stati finiti, equivale ad agggiungere assiomi. Finché questo automa è implementato su una macchina di turing, e non come hardware dedicato, è comunque soggetto al teorema di Godel.

Questo significa che, se usi un algoritmo, interpretato o compilato, su una macchina generica, allora sei soggetto al TdG. Se invece crei un circuito "specializzato" che si occupa solo dell'algoritmo, potresti non essere soggetto. Comunque, devi tener conto che esiste l'instabilità numerica. Spero di aver chiarito. --BW Insultami 08:18, Set 26, 2005 (CEST)

PS: per ogni insieme calcolabile, esiste una macchina di Turing per risolverlo, in generale (Tesi di Church-Turing), ma in ogni insieme ricorsivo, e quindi calcolabile tramite funzioni ricorsive, e quindi tramite macchina di turing, esiste anche almeno un elemento per cui non è possibile dimostrare, all'interno degli assiomi utilizzati per definire l'insieme, che esso appartiene all'insieme, pur appartenendovi (teorema di Matyiasevich). Ossia per ogni problema calcolabile esiste una macchina di turing, che però non può calcolare tutte le possibili varianti del problema. Per fare il paragone con l'aritmetica: per ogni insieme di assiomi coerenti, è possibile verificare se le affermazioni sono vere o false. Per ogni insieme di assiomi, però, esistono dei teoremi (affermazioni) palesemente veri o falsi, che non è possibile dimostrare all'interno delgi assiomi (teorema di Godel). È chiara la differenza tra quanto dici tu, e quanto afferma il teorema? Per inciso, la Tesi di Church-turing non è dimostrabile, proprio per lo stesso motivo. --BW Insultami 08:28, Set 26, 2005 (CEST)

PPS:Tanto per chiarire: Turing ha dimostrato che la MdTu può simulare l'evoluzione di qualunque MdT, anche di sé stessa. Quindi parlare di problemi della MdTu, equivale a parlare dei problemi di tutte le MdT. La dimostrazione è sull'articolo di turing "On computable numbers, with an application to the entscheidungsproblem". --BW Insultami 09:25, Set 26, 2005 (CEST)

Hai qualche link sulla formulazione originaria del teorema? Perché formulato così mi sembra appunto falso. Infatti credo che si possa formulare anche come: Non esistono insiemi ricorsivi (altrimenti l'algoritmo che lo calcola sarebbe un controesempio). Comunque non riesco a seguirti in alcuni passi del ragionamento:

Perché dici che si devono aggiungere assiomi per ottenere formalismi meno potenti dalla MdT? A me sembra che si ottenga lo scopo anche ignorando alcuni degli assiomi disponibili, ad esempio scorrendo sempre avanti il nastro.
Ho capito che nel caso di calcoli numerici come sqrt(2) non avremo mai il risultato corretto, ovviamente perché l'output è infinito. Se non ricordo male la formulazione del problema di terminazione riguardava input e output finiti..
Forse è meglio se chiariamo cosa intendiamo per algoritmo. Per me è: macchina di Turing (secondo la definizione), cioè un programma "cablato"; può essere anche una MdTu (ma non è necessario) ed è identificata dalla sua codifica T per una MdTu. Se inserisci delle "istruzioni" per mandare in loop la MdTu stai in realtà eseguendo un altro algoritmo.
Nell'aritmetica non è possibile dimostrare affermazioni vere (TIG) ma questo perché il problema è indecidibile (non ricorsivamente enumerabile). Stiamo parlando invece di problemi semidecidibili (ricorsivamente enumerabili). Banus 14:08, Set 26, 2005 (CEST)

Allora: ho recuperato gli appunti delle lectures del MIT, che ho seguito come semplice uditore, dove è stato discusso. Ecco in breve la dimostrazione, che usa il T. di Matiyasevich (TdM)

La Macch. di Turing universale può simulare qualunque Mdt, anche sé stessa.
Per definizione, una macchina di turing "calcola" un algoritmo A
Sempre per definizione le funzioni calcolabili sono appunto quelle implementabili da Mdt, quindi A corrisponde ad una qualche funzione calcolabile f_c
Per la tesi di Church-Turing ogni funzione calcolabile è generabile tramite funzioni ricorsive, quindi esiste una funzione ricorsiva f_r equivalente alla f_c, che a sua volta equivale ad A
per il TdM, nell'insieme ricorsivamente enumerabile R generato da f_r, e quindi da A, esiste un elemento $e\in R$ che non può essere calcolato da funzioni ricorsive, e quindi nemmena da A.

Ora, che significa? Se usi un macchina di Turing universale, sei soggetto sia a possibili loop infiniti, sia all'errore di stabilità numerica, per cui in entrambi i casi l'algoritmo, pur corretto, non termina sul risultato, matematicamnte corretto, del calcolo, come per sqrt(2). Se invece usi una MdT non universale, te la puoi cavare (sempre che non sia comunque soggetto alla stabilità numerica). Ma siccome la MdT non universale non può essere programmata per eseguire qualunque compito, ma solo un determinato compito ed equivalenti, la cosa è di scarsa utilità: infatti non riguarda i linguaggi di programmazione, nè la teoria degli algoritmi "implementati" su macchine universali: riguarda solo la costruzione di specifici "hardware" che fanno solo quel compito.

Riguardo ai tuoi dubbi sugli insiemi ricorsivi, sono gli stessi che hanno assalito la comunità matematica quando, nel 1970, Matyiasevich ha dimostrato il suo teorema. In realtà il teorema è semplicemente l'estensione del teorema di Godel alle funzioni calcolabili: anche per la macchina di Turing universale, esistono cose che non può calcolare, altrimenti, ad esempio, potrebbe calcolare il valore di verità della frase di Godel "questa frase non può essere dimostrata", il che è assurdo. Ti suona logico?

Riguardo all'aggiunta di assiomi, una macchina di Turing universale è equivalente all'aritmetica, in quanto posso implementare qualunque teorema dimostrabile tramite un'apposita macchina di Turing. Se io "limito" la macchina ad input di 16 bit, questo è un altro assioma: tutti quelli della MdT, più l'assioma "l'input è di 16 caratteri massimo". Resta comunque una MdT universale, infatti anche per i PC a 16 bit esistono librerie che per permettono di fare i calcoli con qualunque precisione, basta avere pazienza :) Stesso discorso se limito anche l'output, la memoria etc. Fammi sapere. --BW Insultami 08:03, Set 27, 2005 (CEST)

Mi puoi spiegare come si deduce "esiste $e\in R$ non calcolabile da funzioni ricorsive" dal TdM, soprattutto nel caso in cui l'equazione diofantina associata a R è completamente risolvibile? Non riesco a trovare un modo, né trovo riferimenti sulla rete.
Riguardo a Godel OK, ma perché l'insieme delle formule vere non è ricorsivamente enumerabile.
Per finire: provo a fare un esempio concreto. Considera un programma per i nostri PC (approx MdTu) fatto così: unica istruzione, esci(). E' un algoritmo (corrisponde a precise istruzioni macchina) ma, salvo malfunzionamenti hardware, termina sempre. Per fare quello che dici dovresti "taroccarlo al volo" durante il caricamento, ma così (penso che tu sia d'accordo) stai cambiando programma. Volendo, potresti mandargli tutte le istruzioni di Word ;) Ciao Banus 09:51, Set 27, 2005 (CEST)

Ovvio: tra tutte quelle che hanno soluzione la soluzione s, posso trovarne una che non sia risolvibile tramite funzioni ricorsive. Se vedi l'inizio della discussione con MGC c'è questa parte:

"Poiché lavoriamo su numeri interi, ossia input, è possibile associare ad ogni input un numero intero positivo, diciamo i, e quindi, detto I lo spazio dell'input, $i\in I$ . Giusto? È possibile fare lo stesso con l'output o, con $o\in O$ . Ogni possibile risultato e solo quelli sono in O. E fin qui, tutto bene. L'algoritmo, allora, non è nient'altro che una funzione ricorsiva f, $f:I\rightarrow O$ . Se I è ordinato, cosa banale, perché basta il semplice ordine dei numeri interi positivi, allora O è ricorsivamente enumerabile, basta applicare la f, ossia l'algoritmo, agli i ordinati, per ottenere un ordine in O. Ci sei? Ora, vediamo come possiamo reinterpretare la cosa. Consideriamo dei polinomi particolari, come $ax^{2}+by^{2}=cz^{2}$ , ma con qualunque numero di variabili (x,y,z) e di qualunque grado: diciamo $g(x_{1},x_{2},...,x_{n})$ . Ora n, intero positivo, è soluzione di quel polinomio se g(n)=0. Queste n sono le soluzioni delle equazioni diofantee. Ora, siccome prendo O che è ricorsivamente enumerabile, come abbiamo visto prima, posso associare ogni o ad un'equazione diofantea g, la cui soluzione è appunto o. Chiaro? Ora, immaginiamo una funzione h che associa ogni f ad una g: la composizione $h(i)=g[f(i)]$ trasforma ogni input in un'equazione diofantea, il cui insieme G è ricorsivamente enumerabile, visto che lo è I. Di conseguenza lo è H, e h(i)=0 se e solo se g(o)=0. Bene, Matyiasevich ci dice che, in un insieme siffatto, esiste una h di cui non è possibile dimostrare che i è una soluzione. E dato che i genera o, esiste un output che non si può dimostrare raggiungibile da un input i."

Non mi sono chiari alcuni passaggi. g è in genere dipendente da o, giusto? Quindi identifica un insieme di funzioni g_o, e abbiamo h_o(i) = 0 se f(i)=o. G = {g_o | o = f(i)} sempre se ho capito bene. G in genere è un sottoinsieme di tutte le equazioni diofantee (D). Ora per applicare il teorema dovresti avere G = D, ma questo non è verificato in generale. Nell'esempio di Moongateclimber basta un'equazione di primo grado con un'unica soluzione (x - 1 = 0).

Alternativamente potrei considerare G = {x | g_o(x) = 0}, ma a questo punto non vedo come si dovrebbe applicare il TdM --Banus 14:01, Set 27, 2005 (CEST)

Per il tuo esempio: hai mai provato a vedere cosa succede compilando una cosa del genere:

void main(void){
return;
}

Ecco qui:

.file "esci.c" .def ___main; .scl 2; .type 32; .endef .text .p2align 4,,15 .globl _main .def _main; .scl 2; .type 32; .endef _main: pushl %ebp movl $16, %eax movl %esp, %ebp subl $8, %esp andl $-16, %esp call __alloca call ___main leave ret

Visto che non abbiamo input, dobbiamo consideraro lo stato della macchina, ossia memoria e registri. Il trucco sta nell'IP, un po' il metodo usato nei buffer overrun e negli shellcode: se l'IP viene sovrascritto,ed ecco che potrebbe puntare indietro al push, continuando a fare push, call, pop, push, call, pop...

Come si può applicare il buffer overrun se il programma non accetta nemmeno un input? Certo, si potrebbe cambiare l'IP manualmente, ma così cambi l'algoritmo: ad esempio, se il programma è implementato da una M1, potresti ottenere l'algoritmo implementato da una M2 del tutto analoga a M1 ma con stato iniziale diverso. E comunque in quel caso, o si inteferisce con l'hardware o si aggiunge un altro programma in esecuzione sulla MdTu: stiamo uscendo dalle ipotesi di partenza. --Banus 14:01, Set 27, 2005 (CEST)

Non discuto che si potrebbe fare meglio, a mano, ma non si scappa dalla trappola dell'IP. Certo in casi del genere il teorema ci dice solo che nessun programma è immune da errori di sistema. Ad esempio, io posso scrivere:

section .text
global _main
_main:
ret

E compilare. O ancora meglio, in DOS, creare un file di un byte con il solo valore "C3" e chiamarlo esci.com

Ma questa *non è* la macchina di Turing che va in loop: è il sistema che lo esegue che potrebbe andare in loop! Non è l'algoritmo in sé a non terminare, è l'esecuzione di un algoritmo su di una macchina di Turing universale che introduce la possibiltà che non termini. Non so se è chiara la differenza. --BW Insultami 11:19, Set 27, 2005 (CEST)

Se stai dicendo che un algoritmo può terminare per ogni input, ma non se eseguito su una MdTu, non significa che l'implementazione è errata, perché esistone almeno un caso in cui la MdT associata dà un risultato, e l'esecuzione sulla MdTu no? Non riesco a immaginarmi un caso in cui esci.com non termina dato lo stato dell'IP corretto (in caso contrario non stai eseguendo esci.com) --Banus 14:01, Set 27, 2005 (CEST)

E chi ha mai detto che l'implementzione è errata? dico solo che, per ogni algoritmo eseguito su una macchina di turing universale, esiste almeno uno stato della macchina di turing (e non è detto che sia dell'algoritmo in sè) per cui questo non termina. Riguardo Godel e le proposizioni vere, tra l'altro, ecco una breve prova che sono ricorsivamente enumerabili (si può fare meglio, vedi "Godel,Escher e Bach: un'eterna ghirlanda brillante" di Hofstadter, che usa l'aritmetica tipografica)

Ogni proposizione vera è certamente esprimibile a parole.
associo ad ogni simbolo tipografico un numero, ad esempio il suo codice ASCII
interpreto la stringa numerica corrispondente come un intero in base 16: ad ogni proposizione corrisponde un diverso numero, in quanto frasi diverse
Ordino gli interi per grandezza
Metto le proposizioni così ordinate in relazione 1:1 con i numeri naturali
Dato che N è ricorsivamente enumerabile, lo sono anche le proposizioni vere.

CVD

Ho preferito appunto darne una dimostrazione tramite Godel, perché è più immediata di quella con matiyasevich. Inoltre sono dimostrazioni di esistenza, e non costruttive. Sarebbe bello trovarne una, ma credo sia complicato e dipendente dalla macchina di turing utilizzata. Comunque ci penso. --BW Insultami 07:52, Set 28, 2005 (CEST)

Ti sto dicendo che le tue affermazioni contraddicono la mia definzione di algoritmo. Vorrei che tu mi dicessi in quale punto il mio ragionamento o la mia definizione sono sbagliati.
Riguardo alle proposizioni vere, sarei d'accordo con il tuo ragionamento se si potessero distinguere le formule vere da quelle false. Si può ricorrere a una procedura di dimostrazione, ma il GID assicura che ne perdi sempre qualcuna (come asserisce il Teorema di Tarski).
Ora, preferirei che qualcun'altro si inserisse nella discussione. Qui probabilmente uno di noi compie un errore di ragionamento o più probabilmente non ci intendiamo sui termini; una terza persona aiuterebbe a dirimere la questione. --Banus 10:24, Set 28, 2005 (CEST)

Non è un problema: tu stai semplicemente concordando con me che, pur potendo enumerare ricorsivamente tutte le proposizioni vere, nella maniera descritta sopra, di alcune non possiamo dire che sono vere dimostrandolo: ossia sappiamo essere vere, ma non possiamo dimostrarlo. Te lo dico in un altro modo: se la tesi di Church-Turing è vera, le funzioni calcolabili (algoritmi) coincidono con quelle ricorsive. In questa definizione di algoritmo, che non so se è la tua, qualora gli algoritmi vengano eseguiti su una macchina di Turing universale, il risultato dell'elaborazione è soggetto al teorema di Godel: pur sapendo che l'algoritmo è totale e termina per tutti gli input, non possiamo "dimostrarlo" tramite una macchina di turing universale, ossia che l'esecuzione dell'algoritmo, per ogni stato iniziale della macchina di Turing universale che lo esegue, include anche che c'è almeno uno stato per cui la macchina non raggiunge il risultato: o perché sbaglia (stabilità numerica) o perché va in loop. --BW Insultami 11:19, Set 28, 2005 (CEST)

Il problema è che serve una funzione per generare formule vere, o per riconoscerle: per il teorema di Tarski non è possibile trovare una tale funzione, quindi l'insieme è indecidibile secondo la definizione; solo le formule dimostrabili sono R.E. Riguardo alla terminazione, il problema è irrisolvibile in generale, ma questo non vieta che in casi particolari sia possibile dimostrare la terminazione di un algoritmo per tutti gli input. --Banus 12:49, Set 28, 2005 (CEST)

Quello che dici è in contrasto con il teorema di Godel. La frase di Godel è vera, ma non è dimostrabile. Il teorema dimostra che la verità della frase è indimostrabile, non che è vera. È vera perché la frase è «"non è dimostrabile se preceduta dalla sua menzione" non è dimostrabile se preceduta dalla sua menzione». Quindi il tuo assunto che serva una funzione non è vero in generale, il teorema di Tarski ci dice appunto che non puoi trovare tutte le frasi vere con una funzione. L'insieme delle frasi vere comprende almeno un elemento, equivalente alla frase di Godel, che non può essere raggiunto da funzioni o da algoritmi. Ciò non toglie che le frasi vere siano ricorsivamente numerabili, in quanto posso metterle in corrispondenza con N. Io non dimostro, nè potrei farlo, che sono tutte vere, dimostro solo che per ogni frase appartenente all'insieme delle frasi vere, e quindi vera per ipotesi, posso trovare un numero naturale N distinto da tutti gli altri, e quindi ordinandoli, esse stanno in relazione 1:1 con N, (la cardinalità delle frasi vere è $\aleph _{0}$ ) e che quindi, pur essendo ricorsivamente enumerabili, almeno una è irragiungibile. Ti ripeto che puoi dimostrare la terminazione per ogni stato per uno specifico algoritmo, ma non per una macchina di turing universale. Inoltre alcuni algoritmi sono calcolati da (equivalenti a) macchine di turing universali, quindi quanto dici non vale nemmeno per tutti gli algoritmi. Stai focalizzandoti sull'algoritmo e non sul sistema che lo calcola. Ti ripeto che hai ragione se l'algoritmo non è equivalente ad una macchina di turing universale, e implementi la macchina di turing come attrezzo a sé stante. Se la calcoli mediante una MdTu, la cosa è differente. --BW Insultami 13:27, Set 28, 2005 (CEST)

La definizione di R.E. richiede la corrispondenza (o equivalentemente l'enumerazione) mediante una funzione ricorsiva, cioè un algoritmo; siamo d'accordo che questa non esiste, quindi le frasi vere non sono R.E. La tua dimostrazione precedente non è una dimostrazione che l'insieme delle frasi vere è numerabile (come appunto affermi dopo)?. I due concetti sono differenti.
Se esiste un algoritmo che termina per ogni stato (e per ogni input finito) come dici, allora abbiamo un controesempio al teorema di inizio pagina. L'asserzione diverrebbe esistenziale. Oppure dovresti specificare: ogni algoritmo Turing-completo. --Banus 13:43, Set 28, 2005 (CEST)

Quello che richiedi tu sono le condizioni per essere un insieme ricorsivo. Esistono insiemi ricorsivamente enumerabili, ma non ricorsivi. Io ti ho dato l'algoritmo, o funzione, che trasforma ogni elemento dell'insieme V delle proposizioni vere, che certamente esiste, in un elemento di N, e quindi ne ho dimostrato la corrispondenza(per ogni N, esiste una ed una sola proposizione vera). Diverso è che tu non sappia costruire V, e cioè l'enumerazione. Ma è sufficiente la corrispondenza per avere un insieme ricorsivamente enumerabile. Un esempio è l'insieme K del problema della fermata, di cui questo è un'estensione.

Riguardo alla differenza Algoritmo e algoritmo turing-completo, sono giorni che ripeto che deve essere un algoritmo eseguito da una macchina di turing universale, per non terminare. --BW Insultami 07:51, Set 29, 2005 (CEST)

PS: Ovviamente un punto debole del ragionamento è che funzioni calcolabili e ricorsive siano la stessa cosa. Cioè la tesi di CT. Il tutto ci porta a dire che "se la tesi di CT è vera, allora...". Quindi se tu dimostrassi che un algoritmo turing-completo, o una macchina di Turing universale, riesce a raggiungere qualsiasi stato finale ammesso, cioè termina per qualunque stato iniziale, o non dà mai risultati approssimati, in un tempo finito, avresti paradossalmente dimostatrato che la tesi di CT è falsa. --BW Insultami 07:51, Set 29, 2005 (CEST)

Non ci siamo, in insieme ricorsivo e insieme ricorsivamente enumerabile leggo una definizione diversa. Non basta dire che la funzione enumeratrice esista, deve essere anche ricorsiva. Algoritmo Turing-completo vedilo come "emulatore universale", per esempio la regola 110 di Wolfram; la terminazione per ogni input in questo caso equivale al teorema di Turing. Ma non tutti gli algoritmi sono Turing-Completi. --Banus 08:59, Set 29, 2005 (CEST)

È l'inversa della funzione precedente, la quale essendo biettiva, è invertibile sempre, e soddisfa la condizione 1.1 di insieme RE "Esistenza funzione enumeratrice"

Un insieme numerabile S si dice ricorsivamente enumerabile se esiste una funzione calcolabile parziale f tale che S è l'immagine f. --BW Insultami 10:05, Set 29, 2005 (CEST)

Infatti: funzione calcolabile. Avevo capito che era l'inversa, ma se la funzione f: N -> "formule vere" fosse calcolabile, per riconoscere una qualsiasi formula vera basterebbe enumerarle tutte, e fermarsi quando viene trovata la formula data. f è suriettiva (per definizione) quindi se la formula è vera verrebbe trovata in tempo finito (arbitrariamente lungo), e l'algoritmo terminerebbe. E avremmo trovato g ricorsiva (calcolabile) che riconosce tutte e sole le formule vere (e se la formula è falsa non termina, perché sarebbe una funzione parziale). Ovviamente calcolabile è inteso come MdT, cioè data la tesi di Church. Dove sbaglio?
Sugli algoritmi ci siamo chiariti adesso? :) --Banus 10:52, Set 29, 2005 (CEST)

Semplice: la funzione che associa proposizioni -> N è biiettiva, ed esiste la più piccola proposizione vera, usando il codice ascii, che utilizza tre simboli: "0<1", e corrisponde ad un numero, 0x303c31, che corrisponde ad N=1. per trovare la formula associata ad un numero, non devo far altro che costruire tutte le proposizioni a partire da questa, ad esempio la successiva è "0=0", 0x303d30, e via enumerando. Dato che sono permutazioni con ripetizione dei codici (e ne bastano una quarantina, compresi simboli di esistenza, ma possiamo arrivare a 256), a partire da una lunghezza 3, in tempo più o meno esponenziale arrivi a N. Mi sembra una funzione calcolabilissima. --BW Insultami 12:35, Set 29, 2005 (CEST)

Hai bisogno di un oracolo per sapere: questa formula è vera, questa no, etc. perché una funzione computabile che esegua questo non esiste, come afferma il T. di Tarski. Infatti il modo che proponi va bene per controllare le formule ben formate, o quelle dimostrabili (vere o false) a partire da determinati assiomi (basta costruirle secondo determinate regole), mentre per quelle vere saresti costretto a controllare tutte le volte un elenco infinito di assiomi (già disponibile, perché questo insieme non sarebbe computabile, come prevede il GID); oppure avere già disponibile l'elenco (infinito) di tutte le formule vere. Questo perché per avere la nozione di verità devi fissare una particolare interpretazione, e un numero finito di assiomi non è sufficiente a individuarla. --Banus 13:55, Set 29, 2005 (CEST)

Hai bisogno di un oracolo anche per K, per sapere se il programma termina. Ciò non toglie che K sia ricorsivamente enumerabile. È esattamente la stessa cosa. comunque, non voglio convicerti a forza. Anche per il fatto che sono oberato di lavoro, lasciamo decantare un po' la cosa, poi ci ritorniamo. --BW Insultami 07:50, ott 10, 2005 (CEST)

Wikipedia:Bar/Dimostrazione alternativa

Menu di navigazione

Ricerca