Title: Linguaggi di Programmazione Primo Semestre / 16 - Cenni di Calcolabilità

Q: Halting Problem
A: Definizione Problema:
Dimostrazione:

Proprietà indecisibili determinanti dall'halting problem

Def: Macchina di Turing

Def: Macchina di turing mossa e stato, linguaggio accettato

Def: di turing calcolabile

Cardinalità funzioni di calcolabilità

Teorema di Jacopini-böhna

Tesi di chrnch-turing