Perché questo è una macchina di Turing non valida?

Question

Mentre facendo revisione esame Sto avendo difficoltà di rispondere alla seguente domanda dal libro, "Introduzione alla teoria della computazione" di Sipser. Purtroppo non c'è una soluzione a questo problema nel libro.

Spiegare perché seguenti non è una macchina di Turing legittima.

M = {

L'ingresso è un polinomio p sulle variabili x1, ..., xn

1. Prova tutte le possibili impostazioni di x1, ..., xn a valori interi
2. Valutare p su tutte queste impostazioni
3. Se uno qualsiasi di queste impostazioni viene valutata a 0, accettare; altrimenti respingere. }

Questo mi sta facendo impazzire! Ho il sospetto che sia perché l'insieme degli interi è infinito? Questo in qualche modo supera dimensioni consentite dell'alfabeto?

Answer 1

Anche se questo è un modo del tutto informale, di descrivere una macchina di Turing, direi che il problema è uno dei seguenti:

• otherwise reject - Sono d'accordo con Welbog su questo. Dal momento che si dispone di un insieme infinito numerabile di possibili impostazioni, la macchina può mai sapere se un ambiente su cui si valuta a 0 è ancora a venire, e ciclo volontà per sempre se non trova alcuna - solo quando si incontra una tale impostazione, la macchina può arrestare. Che l'ultima affermazione è inutile e non sarà mai vero, a meno che naturalmente si limita la macchina ad un insieme finito di numeri interi.

• L'ordine di codice: Vorrei leggere questo pseudocodice come "Scrivi tutte le impostazioni possibili verso il basso, quindi valutare p su ciascuno" e non c'è il problema: Ancora una volta, avendo un insieme infinito di possibili impostazioni, nemmeno la prima parte sarà mai terminare, perché non è un ultimo un'impostazione di scrivere e continuare con il passaggio successivo. In questo caso, nemmeno la macchina può mai dire "non c'è 0 impostazione", ma non può mai nemmeno iniziare a valutare per trovarne uno. Anche questo sarebbe risolto limitando il set intero.

In ogni caso, non credo che il problema è la dimensione del alfabeto. Non è necessario utilizzare un alfabeto infinita dal momento che i vostri numeri interi possono essere scritti in decimale / binario / etc, e quelli utilizzare solo una (molto) alfabeto finito.

Answer 2

Sono un po 'arrugginito su macchine di Turing, ma credo che il tuo ragionamento è corretto, vale a dire l'insieme degli interi è infinito quindi non tutti possono calcolare. Non sono sicuro di come dimostrare questa teoria, però.

Tuttavia, il modo più semplice per ottenere la testa intorno macchine di Turing è quello di ricordare "Qualsiasi altra cosa un vero e proprio computer può calcolare, una macchina di Turing può anche calcolare.". Quindi, se si può scrivere un programma che dato un polinomio in grado di risolvere le vostre 3 domande, si sarà in grado di trovare una macchina di Turing che può anche farlo.

Answer 3

Credo che il problema è con l'ultima parte: otherwise reject.

numerabili set basi , qualsiasi spazio vettoriale su un insieme numerabile è si numerabile. Nel tuo caso, si dispone di uno spazio vettoriale su interi di n dimensioni, che è numerabile. Così il vostro insieme di interi è numerabile e quindi è possibile provare ogni combinazione di essi. (Vale a dire senza mancare qualsiasi combinazione.)

Inoltre, calcolare il risultato di p su un dato insieme di ingressi è inoltre possibile.

E entrare in uno stato accetta quando p restituisce 0 è inoltre possibile.

Tuttavia, poiché non v'è un numero infinito di vettori di ingresso, è possibile non rifiutare l'ingresso. Pertanto nessuna macchina di Turing in grado di seguire tutte le regole definite nella questione. Senza quella ultima regola, è possibile.