TCC: Tesi di Church - Turing

[Gianluca Di Vincenzo]

Come anche per l'altra domanda che ho postato qualche giorno fa, mi affido a qualche anima pia che naviga spesso su questo gruppo, e la ringrazio ancor prima che risponda.

Come da Titolo chiedo aiuto sulla tesi di Church - Turing, vi incollo alcune domande che il Prof.Mignosi pone nel suo programma dettagliato.

Al Capitolo 8 si associa la tesi di Church-Turing presa dalle dispense del corso disattivato di Fondamenti 1, che dice: "TESI DI CHURCH: PRIMA PARTE: Non esiste alcun formalismo, per modellare una determinata computazione algoritmica, che sia pi u potente delle MT e dei formalismi ad essa equivalenti. 

TESI DI CHURCH: SECONDA PARTE: Ogni algoritmo pu o essere codicato in termini di una MT (o di un formalismo equivalente)." 

 

Saper rispondere alle seguenti domande:

1) Perché ho detto che si associa il Capitolo 8 alla tesi di Church-Turing?

2) L'esperienza di Church sulla cui base Church ha enunciato la tesi, da che cosa era fondata?

3) Per ogni modello di Calcolo noto, esiste un teorema che ne dimostra l'equivalenza con il modello delle

 Macchine di Turing (anche se noi non necessariamente lo abbiamo provato)?

4) Il linguaggio di programmazione C, è equivalente al modello delle Macchine di Turing?

5) C'è un teorema?

(Soluzioni: alle ultime 3 domande la risposta è si. La risposta alla seconda domanda è la versione affermativa della domanda successiva).

Potete trovare la tesi di Church-Turing anche su internet MA non ripetete a "vanvera"!!!.

Ora stranamente so rispondere alla domanda 4) ed il 'SI' della domanda 3) è scontata dopo aver seguito un corso come TCC, ma alle altre non saprei dove mettere mano, c'è qualcuno che mi può cortesemente illuminare :-) 

Vi ringrazio anticipatamente a tutti per le vostre risposte e per la vostra collaborazione :-)