Problema de la fermada
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 Modifega
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à Modifega
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 F(A,B).
K(A) 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 K(K) la fonzion resultanta F(K,K) la retorna vera se K cont input K, ma per definizion se F(K,K) l'è vera K(K) la va in loop, e donca a gh'è on paradoss.
Importanza e conseguenz Modifega
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.