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 
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 .

 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  la fonzion resultanta  la retorna vera se K cont input K, ma per definizion se  l'è vera   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.

 Riferiment 
Problema dell'arresto - Treccani

 Varda anca 
P vs NP
Decidibilità
Categoria:Teoria de la calcolabilità