Discussione:Problema della terminazione

Untitled

Si dice che il problema della fermata è un problema che consiste in... etc. Poi si dice: "Per dimostrarlo..." Ma per dimostrare cosa? Ci vorrebbe una tesi prima di scrivere una dimostrazione. O almeno, scrivere "dimostriamo che... (? che è un problema?)"

• Il problema è stato proposto, e poi dimostrato essere indecidibile. La dimostrazione nella voce è appunto quella della non-esistenza di un algoritmo generale per la soluzione. In effetti prima l'esordio era incorreto, adesso l'ho parzialmente sistemato. Ζεττι­­ ◙

---

L'ho sentito sempre nominare come "problema della terminazione" (halting problem).

• Confermo, anche io ho sempre sentito parlare di halting problem o problema di terminazione

Il termine più usato è "problema dell'arresto", si incontra anche più di 10 volte che "problema della terminazione" (77 000 contro 6 800), ma ho visto che c'è il rivio, allora lasciamo pure così. --176.4.72.59 (msg) 19:58, 21 lug 2012 (CEST) Marco Pagliero Berlin

Termine non spiegato

si inserisce il termine guardia senza spiegarlo!

Un dubbio sulla dimostrazione.

Questa dimostrazione può indurre facilmente all'errore e pertanto perdonatemi se sbaglio.

Quando ho letto questo paradosso l'ho associato a quello di "Achille e la tartaruga".

Nulla da obiettare sulle ipotesi e sui passaggi che si riferiscono alla funzione TERMINA. Se ho ben capito si tratta di un algoritmo che, in un tempo finito, è in grado di analizzare se la funzione A è in grado di terminare oppure no.

Quello che secondo me porta ad una conclusione errata è il passaggio che fa uso del costrutto PARADOSSO (PARADOSSO) (un ulteriore complicazione è aggiunta dall'utilizzo del ciclo WHILE che ha bisogno di un "tempo infinito" per concludere che esso non termina):

PARADOSSO (PARADOSSO) : while (TERMINA (PARADOSSO,PARADOSSO)); Nulla infatti possiamo concludere con riferimento a quest'ultimo costrutto che necessita di "un numero infinito di sostituzioni" per essere risolto. PARADOSSO (A) : while (TERMINA (A,A)); PARADOSSO (PARADOSSO) : while (TERMINA (PARADOSSO,PARADOSSO)) : while (TERMINA (while TERMINA(PARADOSSO,PARADOSSO)), ....) : ....

Analogamente ad "Achille e la tartaruga" è il metodo di calcolo che non ha termine non la funzione. A mio avviso è questa l'origine del paradosso, non indecidibilità della proposizione originale.--188.152.2.14 (msg) 21:45, 29 apr 2011 (CEST)Claudio Marchesan Via Manzoni, Padova

Non è così: non c'è alcuna similarità con il problema di "Achille e la tartaruga" e probabilmente l'aver chiamato un algoritmo PARADOSSO induce a confondersi e per questo adesso l'ho rinominato K. In particolare bisogna fare attenzione che si sta parlando di algoritmi e non di funzioni ed il fatto che K cicli all'infinito è dovuto al fatto che lo si vuole far ciclare all'infinito per costruzione, non che cicla all'infinito perché c'è un "errore nascosto" nell'interpretazione o nella definizione di qualcosa. Mi sono quindi permesso di riscrivere parzialmente la dimostrazione, evitando sia il termine "PARADOSSO" che il termine "guardia" che come accennato da qualcuno più in alto non era stato definito.--92.108.60.219 (msg) 10:35, 22 set 2013 (CEST)