Automi, MdT, tesi Church (LSA)

4. Qual è il ruolo della testina in una macchina di Turing?

• a. Memorizza lo stato corrente
• b. Scrive sul nastro
• c. Si sposta a sinistra o a destra
• d. Legge il nastro e si sposta

5. Quale dei seguenti NON è un componente di una macchina di Turing?

• a. Nastro infinito
• b. Funzione di transizione
• c. Schermo di output
• d. Testina di lettura/scrittura

6. Qual è lo scopo della tesi di Church-Turing?

• a. Definire i limiti dell'intelligenza umana
• b. Stabilire che qualsiasi funzione computabile può essere calcolata da una macchina di Turing
• c. Descrivere la struttura fisica dei computer
• d. Enumerare tutti i possibili algoritmi

7. Quale delle seguenti affermazioni è vera per una macchina di Turing universale?

• a. Può eseguire solo un algoritmo specifico
• b. Può simulare qualsiasi altra macchina di Turing
• c. È una macchina fisica
• d. Non può eseguire operazioni matematiche

10. Quale delle seguenti è un esempio di funzione computabile?

• a. Cacolare il doppio di un numero intero
• b. Prevedere il meteo con assoluta precisione
• c. Determinare se tutte le esecuzioni di un programma terminano o no
• d. Identificare le emozioni umane

15. Qual è la funzione primaria del nastro di una macchina di Turing?

• a. Memorizzare gli output
• b. Fungere da memoria temporanea
• c. Contenere le istruzioni
• d. Fornire input infiniti

16. A cosa si riferisce il termine "computabilità" in informatica?

• a. La velocità di computazione di un programma
• b. La capacità di risolvere un problema utilizzando un algoritmo
• c. Il controllo della correttezza di un algoritmo
• d. La capacità di eseguire le operazioni di calcolo tra numeri binari

19. Quale dei seguenti è un concetto introdotto dalla teoria della computabilità?

• a. Progettazione hardware
• b. Efficienza dell'algoritmo
• c. Allocazione della memoria
• d. Decidibilità

1. Qual è la principale preoccupazione della teoria della computabilità?

• a. Analizzare la velocità degli algoritmi
• b. Decidere sulla computabilità degli algoritmi
• c. Migliorare l'efficienza degli algoritmi
• d. Ridurre la complessità degli algoritmi

5. Qual è una delle operazioni elementari che una Macchina di Turing deve essere in grado di eseguire?

• a. Aggiungere nuovi simboli al nastro
• b. Cancellare il nastro
• c. Spostare la testina di lettura/scrittura
• d. Confrontare dei simboli