Discussione:Macchina che termina sempre

Sposto un po' brutalmente da "macchina che si stoppa sempre"; "stoppa" non e' una parola italiana (e dubito che esista anche *un solo* riferimento bibliografico che usa questa forma). Visto che esiste il problema della terminazione (traduzione standard italiana), mi sembra scontato che questa dizione sia piu' corretta. Moongateclimber 14:14, 23 giu 2006 (CEST)

Lo so, ma ci stavo lavorando, ora devo cancellare sta voce e rispostarla!! Lusum 14:21, 23 giu 2006 (CEST)

Possibile errore nel teorema nella sezione "Confronto con le macchine di Turing parziali"

Buongiorno, scrivo per segnalare un possibile errore nell'enunciato del teorema in oggetto (di conseguenza segnalo anche quello che ritengo essere l'errore nella dimostrazione).

Affermo:

- l'enunciato (*) "Ci sono funzioni totali Turing-computabili che non sono computabili da una macchina che termina sempre" e' falso. E' quindi vera la sua negazione: (**) "ogni funzione totale Turing-computabile e' anche computabile da una macchina che termina sempre". Dimostrazione: Per assurdo, sia f che violi (**). Quindi f e' totale, Turing-computabile diciamo dalla macchina M, ma non computabile da una macchina che termina sempre. In particolare M non termina sempre. Siccome M computa f ed f e' totale si ha per ogni input n, l'esecuzione di M(n) termina (e proprio col valore f(n)). Ma allora M termina sempre. Contraddizione. Cio' basta per dimostrare (**) (ed automaticamente escludere (*))

- la dimostrazione presente nell'articolo dimostra il seguente enunciato: (***) "L'insieme delle macchine che terminano sempre non e' ricorsivamente enumerabile". E' quindi falsa la frase che riporto dall'articolo "Dal momento che ogni descrizione porta la macchina a terminare in qualche punto, non è difficile vedere che l'insieme di descrizioni della macchina D che porta alle funzioni totali è un ricorsivamente enumerabile". La dimostrazione di (***) e' come segue. Per assurdo, sia l'enunciato (***) falso. Allora l'argomento riportato nell'articolo funziona, e si trova una contraddizione a (*).

- probabilmente gli autori si sono confusi con la dimostrazione del seguente: (****) "Esistono funzioni totali Turing-computabili che non sono primitive ricorsive". Per quanto questo fatto possa anche sembrare ovvio oggi, non lo era certo agli inizi della calcolabilita' e percio' quest'affermazione ha tuttora lo status di teorema. Vi sono almeno due dimostrazioni classiche: (1) la funzione di Ackermann e' totale ma non primitiva ricorsiva; (2) per diagonalizzazione. Quella a cui eventualmente si sarebbero rifatti gli autori dell'articolo e' la (2). Notare che siccome la nozione di "primitivo ricorsivo" e' sintattica, si ha che in effetti l'insieme delle macchine che implementano programmi primitivi ricorsivi e' ricorsivo enumerabile (vedere nota [1]). Interpretata in quest'ottica, la dimostrazione dell'articolo produce una funzione totale ma non primitiva ricorsiva.

[1] Notare che vi e' una sottile distinzione tra i due concetti: (1) implementare un programma primitivo ricorsivo (PR); (2) computare una funzione PR. Infatti, un programma PR e' un programma che usa solo cicli FOR (cioe' che hanno un bound sul numero di iterazioni---contrapposto al ciclo WHILE che puo' eseguire all'infinito), e per f PR esistono sia implementazioni che usano solo il ciclo FOR che implementazioni che usano anche il ciclo WHILE. L'elenco delle macchine che implementano programmi PR e dichiarato essere ricorsivo enumerabile e' intuitivamente quello ottenuto elencando tutte le macchine, leggendo il loro programma e determinando se contiene almeno un WHILE, in tal caso escludere la macchina dall'elenco. Val la pena osservare che l'elenco delle macchine che computano funzioni PR non e' ricorsivo enumerabile.

Aspetto commenti da voi appassionati informatici teorici!

Distinti saluti, Michele

se ritieni che la voce sia errata puoi correggerla quando vuoi :) Lusum scrivi!! 20:25, 11 set 2014 (CEST)

==Non sono riuscito a decifrare il senso di due frasi per sistemarle meglio. Qualcuno che ha dimestichezza con questo argomento può dare il suo contributo? L'enciclopedia deve essere scritta in modo sufficientemente chiaro da consentire la comprensione della voce a chi, pur possedendo le nozioni di base per capirla, non la conosce ancora. --Angelo Mascaro (msg) 19:26, 16 set 2019 (CEST)