Problemi universale Macchina di Turing

Question

Se ho una macchina, lo chiamano macchina 1, che è in grado di risolvere un problema: è solo una macchina, non è di per sé una macchina di Turing. E 'in grado di risolvere un problema specifico. Se questo esatto lo stesso problema può essere risolto su una macchina di Turing universale, quindi è la mia macchina originale, 1, una macchina di Turing universale troppo?

Questo non vale per tutti i problemi, che è già ansered. Ci sono problemi che hanno questa descritta proprietà a tutti? Se non è assolutamente vero, allora perché?

Qualcuno può dare un esempio di un problema da risolvere. Se il problema viene risolto con la mia macchina originale, 1, rende sicuramente questo tornio un universale? Oppure un tale problema non esiste? Se non esiste, perché?

Sono molto interessato, ma non riesco a capirlo ... Grazie.

Modifica:. Reso la questione più chiaro

Answer 1

Il punto del universale CNC (UTM) è che per ogni macchina di Turing (TM) si poteva prendere che la MT e creare una codifica per esso che descrive il funzionamento della TM e che hanno eseguire la codifica su un altro TM.

L'UTM è una MT che ha una definizione sufficientemente potente tale che qualsiasi altra definizione TM potrebbe essere riscritto in esso.

Si pensi alla UTM come interprete. TM è un compito specifico.

A meno che la TM è anche nella classe degli interpreti allora non è un UTM pure. (Poiché un UTM è anche un TM specifico compito).

Quindi, per rispondere alla tua seconda domanda: se si può dimostrare che l'UTM e TM sono equivalenti allora avete dimostrato che TM è anche un'UTM. Per fare questo è necessario essere in grado di mostrare come un programma codificato per l'UTM può essere cambiato in un programma equivalente per la TM.

Answer 2

Una macchina di Turing universale in grado di risolvere qualsiasi di una vasta classe di problemi.

Se la macchina (1) in grado di risolvere 1 + 1, ciò non significa che si può risolvere qualsiasi della classe enorme. Quindi non può essere un Universal Macchina di Turing.

Answer 3

I logici distinguono tra condizioni "neccessary" "sufficiente" e. Prendiamo, per esempio, la frase

  

Il cielo è blu.

(facciamo solo per scontato che è sempre vero). Quello che si sa ora è questa:

  

Quando si guarda il cielo, si vede il colore blu.

Quello che non sapere è questo:

  

Quando si vede il colore blu, si sta guardando il cielo.

-. Si potrebbe anche essere guardando macchina del vicino

In termini logici, il colore blu è neccessary per il cielo, ma non è sufficiente.

Lo stesso vale per il vostro caso: macchina (1) non risolve il problema, quindi è davvero un problema risolvibile. Quindi, essendo in grado di risolvere il problema è un neccessary condizione per un UTM, ma non sufficiente, perché un UTM deve essere in grado di risolvere qualsiasi problema (che è risolvibile a tutti), non solo questo singolo.

Answer 4

una macchina di Turing universale in grado di risolvere qualsiasi codice che qualsiasi macchina di Turing specifico può risolvere.

Così la vostra macchina di Turing universale (2) in grado di risolvere il problema che la macchina di Turing originale (1) è stato progettato per risolvere.

La macchina di Turing originale (1), tuttavia può risolvere solo il problema esatto e non in grado di risolvere qualsiasi altro problema (tra cui il "problema" di essere una macchina di Turing universale).

Quindi no, la macchina di Turing originale non è una macchina di Turing universale in base alla descrizione. (Potrebbe essere se la si definisce, ma questo è il tipo di truffa).

Answer 5

  

Qualcuno può dare un esempio di un problema da risolvere.

Certo:. Dato tornio codificato e dei dati, qual è il risultato :) Se la macchina è in grado di risolvere questo problema, è sicuramente UTM

Non si conosce il motivo per cui la linea di ragionamento questi diversi problemi sono in NP? Come 'posso risolvere il problema 3-sat quando ho una macchina che risolve il problema di Hamilton?' Si può sicuramente utilizzare lo stesso per rispondere alla tua domanda.

Answer 6

A dimostrazione della completezza di Turing di un particolare sistema non è banale, a meno che non si può facilmente dimostrare che è equivalente / isomorfo a un altro sistema che è sapere di essere Turing completo. Così risposta breve: non v'è alcuna prova semplice che si può mettere la macchina attraverso per verificare se si tratta di Turing completo. Bisogna analizzare e mostrare le proprietà del sistema nel suo complesso.

Se volete saperne di più su questo argomento, leggere questi articoli su Turing completezza teoria della computabilità .

Answer 7

Immaginate un UTM come se come è possibile procedere se si deve scrivere un codice (ad alto livello) per simulare il turing machine.You richiederà la seguente: 1.Array per contenere i simboli di ingresso e la roba che yiu avrebbe fatto su di esso. 2.An matrice (possibile 2-d) per tenere la funzione di transizione che si richiederà all'utente. algoritmo 3.An che leggere dati da parte dell'utente di funzioni di transizione e simula sulla matrice 1. variabili 4.Few che il programma avrà bisogno di monitorare il proprio stato.

Se si pensa in questo modo, se si finisce per ottenere un perfettamente il codice di lavoro si finisce con un UTM perfetta. Tuttavia, il problema è, non importa quanto in modo efficiente si codifica non si può fermare l'utente di entrare funzioni di transizione che può causare il codice per eseguire forever.So ci saranno alcuni problemi per i quali fallirà UTM, e poi diciamo che per quei problemi non siamo in grado di sviluppare una macchina per la prova di appartenenza. (anche se nota una macchina di verifica di appartenenza è sempre possibile)