Problema de la fermada
Modell:MILCLASS El problema de la fermada a l'è on problema de l'informatega e de la teoria de la computabilità che 'l domanda:
- Daa on algoritm e 'l sò staa inizial a l'è possibil savè se l'algoritm el finiss el sò process o el va innanz a l'infinii?
In del 1936 l'Alan Turing l'ha provaa che a l'è impossibil avègh on algoritm general per verificà 'sta situazion, e che donca el problema de la fermada a l'è, in su la macchina del Turing, indecidibil.
Definizion formala
Daa on numer de Gödel de fonzion computabil,
Cont i Fonzion de copia de Cantor,
L'insemma l'è ciamaa "insemma de fermada"
El problema de decid se l'insemma de fermada a l'è recorsiv a l'è el problema de la fermada. Vist che l'è recorsivament numerabil, el problema a l'è no resolvibil in di fonzion computabil.
Dimostrazion de indecidibilità
Ciappom per assurd on algoritm che, daa on algoritm e on valor finii, el capiss se l'algoritm el termina o el va innanz a l'infinii, ciamaa Modell:Code.
Modell:Code inveci a l'è ona fonzion che la va in loop de F(A,A) a l'è vera, e la se ferma se l'è falsa.
Se ciamom Modell:Code la fonzion resultanta Modell:Code la retorna vera se K cont input K, ma per definizion se Modell:Code l'è vera Modell:Code la va in loop, e donca a gh'è on paradoss.
Importanza e conseguenz
A l'è important perchè a l'è staa vun di primm problema a vess demostraa indecidibil.
Vuna di conseguenz pussee important de 'sta situazion a l'è che ghe pò no vess on algoritm unich per confermà i affermazion in sui numer naturai.
Per el derivaa Teorema de Rice tucc i affermazion in su on algoritm che hinn no banai a pòden vess no deciduu. Se parla ciarament a nivell de teoria, vist che in pratica, cont di mezz, a l'è possibil fàll in l'implementazion de l'algoritm.