La macchina di Turing può essere classificata? [chiuso]

Per la tua prima domanda, considera, ad esempio, la definizione formale di una macchina Mealy di Wikipedia. La tua domanda è esattamente equivalente a "può una macchina di Turing essere descritta in termini di quella definizione?" Guardare una definizione formale di una macchina di Turing sarebbe istruttivo.

Per la tua seconda domanda, potresti voler cercare Universal Turing Machines. Sono una formulazione di quasi l'idea di "inserire una macchina di Turing in un'altra macchina di Turing", e qualsiasi risorsa ragionevole che discuta quelle più che di passaggio ti aiuterà sicuramente a darti un'idea di come si rapporta il problema dell'arresto.

Questo suona terribilmente come un compito a casa, quindi mi asterrò dal dare una risposta più dettagliata, ma considerando l'inserimento di una macchina di Turing:

• Puoi codificare ogni macchina di Turing in una stringa (leggi i numeri di Gödel su quello)
• Il problema di blocco diventa sempre un problema, se una macchina di Turing è simulata / in esecuzione in qualche modo.
• Quando si inserisce una stringa in un'altra macchina di Turing, la stringa può codificare una macchina di Turing, ma nessuno dice che deve eseguire questa macchina di Turing. Quindi la tua seconda domanda è essenzialmente inutile, dato che puoi ovviamente inserire una stringa su una macchina di Turing.