Computabilità e MdT

Quali sono i compiti per ognuno dei soggetti seguenti

1. Programmatore: traduce un algoritmo in un programma sorgente

2. Esecutore: a partire dall'eseguibile e dai dati del problema produce la risposta attesa

3. Risolutore: produce un algoritmo per un problema dato

4. Compilatore: traduce un programma (file) sorgente in un programma (file) eseguibile

La tesi di Church afferma che tutti i problemi risolubili ammettono come algoritmo un'appropriata Macchina di Turing

Un problema è computabile se esiste un algoritmo, per un certo esecutore, che produce le risposte attese per ogni istanza del problema

Cosa s’intende per linguaggi di alto / basso livello: ...