Stavo leggendo un capitolo sulle funzioni LOOP -commutabili e ho la seguente domanda: Is è possibile numerare ogni programma LOOP con un algoritmo?
Formalmente: è possibile avere un programma LOOP M, st M (n, m) = P_n (m) (l'input è n, m l'output è P_n (m), dove P_n è la numerazione dei programmi del ciclo ).
No. Supponiamo che M sia un programma di loop. Definire il programma D (x) = M (x, x). Quindi D è banalmente un programma di loop. Sia I l'indice di D nell'enumerazione, cioè P_i = D; allora M (i, i) non si ferma perché è un ciclo infinito (D (i) chiama M (i, i) chiama D (i) ...). Pertanto M non può essere un programma di loop.
Leggi altre domande sui tag functions functional-programming algorithms