Problema de la fermada

Quest articol chì l'è scrivuu in lombard, grafia milanesa.

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 $\varphi$ de fonzion computabil,

Cont $\langle i,x\rangle$ i Fonzion de copia de Cantor,

L'insemma $K_{\varphi }^{0}:=\{\langle i,x\rangle |\varphi _{i}(x)\ \mathrm {esist} \}$ 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 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

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