Come capire se una macchina è equivalente alla macchina di Turing

Question

Ho trovato un articolo di Wikipedia di a list of Turing machine equivalents. Tuttavia, non indica un metodo per determinare se una determinata macchina è equivalente alla macchina di Turing.

Devo utilizzare la definizione di una macchina di Turing per dimostrarlo? Potresti fare un esempio?

Grazie.

Answer 1

Il metodo standard di provare qualcosa di Turing completo è quello di implementare una delle TM-equivalenti in macchina. Se ciò è possibile, la macchina è completa. Se non lo è, allora non lo è. Quindi, se provassi a dimostrare, per esempio, che un nuovo linguaggio di programmazione è completo, sceglierei l'equivalente TM che è il più semplice da implementare, e quindi mostrerò che il mio linguaggio di programmazione può simularlo.

Answer 2

della parte superiore della mia testa: Se la macchina può simulare una delle più conosciute macchine equivalenti macchina di Turing, allora la macchina è anche Turing Machine equivalente.

Probabilmente il modo più semplice per fare qualcosa di simile.

EDIT: Non sto dicendo che questo è un requisito per una macchina per essere macchina di Turing equivalente, alltough potrebbe essere. Forse qualcuno che è un po 'più esperto in informatica teorica può chiarirmi su questo?

Answer 3

In realtà non può essere provato. Almeno, la piena formalizzazione di queste prove di uguaglianza comuni potrebbe richiedere una logica molto più formale di quanto ci si possa aspettare anche nell'informatica teorica. (Se non siete d'accordo, mi dica! Sono ansioso di discutere di questo.)

Tuttavia, è soprattutto chiaro dal contesto. Si tenta di costruire una simulazione di una "macchina" di schema di computazione A all'interno di un altro tale modello di calcolo B. Ciò significa che B può simulare A, e quindi ha la piena potenza di A. Se si fa il contrario, questi due modelli sono chiamati equivalente.