Alcune domande sulla calcolabilità delle macchine Turing

Question

Sto imparando per un test e ho alcune domande importanti sulla calcolabilità delle macchine deterministiche e non deterministiche.

Consideraremo le funzioni parziali $ f, g, h, t: \ mathbb {n} \ reapyraw \ mathbb {n} $ con $ f $ è la macchina per la macchina calcolabile, $ G $ non turing machine computable, $ H $ non è durante la risoluzione di solvibile e $ T $ è aggiornato. Le seguenti risposte sono corrette? E c'è qualcosa che cambia se avessimo un TM non deterministico?

Non ci sono prove per effettuare le parole sono OK :)

.
1. è $ f \ circ in G $ Turing Machine Computable?
2. è $ G \ CIRC F $ Turing Machine Computateble?
3. è $ t \ circt h $ mentre computabile?
4. è $ h \ circ in T $ while computable?

Le mie risposte:

Prima di tutto, sappiamo che Turing Machine= while Computability. (#)

.
1. Direi che non sappiamo se è o non è computabile TM, perché potrebbe esserci un TM che può gestire l'output di una funzione calcolabile non TM.

2. Direi di no, perché se qualunque class class="container per la matematica"> $ G $ prende, non sarà Tm Computable.

3. e 4. A causa di (#) è lo stesso simile a 1. e 2.

potrebbe essere giusto? È per un test a scelta multipla e quelle domande sono complicati.

Answer 1

La risposta è "Non sappiamo senza ulteriori informazioni" per tutti e 4.

Supponiamo $ f $ è la funzione di identità $ f (x)= x $ . Quindi $ f \ Circ G= G \ Circ F= G $ , che non è computabile.

D'altra parte, supponiamo $ G $ è una funzione total non comparibile (che è un caso speciale della classe $ G $ Essere a parziale funzione non computabile) e supponiamo $ f $ è La funzione costante zero $ f (x)= 0 $ . In questo caso:

.
• $ f \ circ in G $ è la funzione costante zero, che è ovviamente calcolabile.
• $ g \ circg f $ è anche una funzione costante. Non sappiamo necessariamente ciò che la costante è , ma non importa; Ogni funzione costante è calcolabile. Vedi Come può essere decidabile Sia $ \ PI $ ha una sequenza di cifre?

La macchina deterministica contro la macchina non deterministica della macchina non deterministica non influisce sulla risposta, poiché una macchina deterministica può simulare l'esecuzione di una macchina di turing non deterministica (potenzialmente con un rallentamento esponenziale) da DOVAILING .