Algumas perguntas sobre a computabilidade das máquinas Turing

Question

Estou aprendendo para um teste e tenho algumas perguntas importantes sobre a computabilidade das máquinas de Turing determinísticas e não determinísticas.

Considere que temos as funções parciais $ f, g, h, t: \ mathbb {n} \ rightarrow \ mathbb {n} $ com $ F $ é computável da máquina de Turing, $ g $ Não Turing máquina computável, $ h $ não é enquanto solucionável e $ t $ é enquanto computável. São as respostas a seguir corretas? E há algo mudando se tivéssemos um TM não determinístico?

Não há prova para fazer palavras são ok :)

.
1. é $ f \ CIRT G $ Máquina de Turing Computável?
2. é $ g \ CIRC F $ Máquina Turing Computável?
3. é $ t \ circ \ circ h $ enquanto computável?
4. é $ h \ CR $ enquanto computável?

minhas respostas:

Primeiro de tudo, sabemos que a máquina de Turing= enquanto a computabilidade. (#)

.
1. Eu diria que não sabemos se é ou não é computável TM, porque pode haver um TM que pode lidar com a saída de uma função computável não TM.

2. Eu diria não, porque se qualquer $ g $ leva, não será computável TM.

3. e 4. Por causa de (#) é o mesmo como 1. e 2.

Isso poderia estar certo? É para um teste de múltipla escolha e essas perguntas são complicadas.

Answer 1

A resposta é "não sabemos sem mais informações" para todos os 4.

suponha $ F $ é a função de identidade $ f (x)= x $ . Em seguida, $ f \ circ. g= g \ circle f= g $ , que é não computável.

Por outro lado, suponha $ g $ é uma função não-computável (que é um caso especial de $ g $ ser uma função não-computável), e suponha $ F $ é A função zero constante $ f (x)= 0 $ . Neste caso:

• $ f \ circ. g $ é a função zero constante, que é obviamente computável.
• $ g \ circ 1 F $ também é uma função constante. Não sabemos necessariamente o que a constante é , mas isso não importa; Toda função constante é computável. Ver como pode ser decidível Se $ \ pi $ tem alguma seqüência de dígitos?

Máquina de Turing não determinista não afeta a resposta, porque uma máquina determinística de Turing pode simular a execução de uma máquina de Turing não determinista (potencialmente com uma desaceleração exponencial) por encaixe .