Como argumentar que, se pudéssemos resolver o problema de interrupção, poderíamos resolver o castor ocupado?

Question

Esta é uma das tarefas da minha tarefa. Eu tenho uma simulação de máquina de Turing que pode simular um Função de castores ocupados. Eu fiz algumas pesquisas sobre provar esse problema, mas ainda não o entendi, então acho que talvez você possa me ajudar aqui. Uma boa fonte para eu ir para ou exemplo de como argumentar que isso seria bom.

Answer 1

A função BB é definida como o número máximo de etapas que uma máquina de Turing de um tamanho específica pode realizar e ainda parar. (Outra maneira de colocá -lo é que todas as máquinas Turing do tamanho X param em etapas menores que BB (x) ou correm para sempre).

Supondo que você tenha uma máquina de Turing de complexidade X, você pode determinar se isso pararia ou não, deixando -o executar para o tempo de BB (x) - se não tivesse parado até então, então, por definição, nunca o fará.

Da mesma forma, se você puder resolver o problema de interrupção, poderá avaliar todas as máquinas de Turing possíveis do tamanho X, eliminar aqueles que não param e consideram o BB (x) para ser o máximo dos tempos de execução dos restos.

Obviamente, o BB (x) não é computável - e, de fato, cresce mais rápido do que qualquer função computável possível que você possa citar - portanto, não pode nem ser aproximado.

Answer 2

Você pode encontrar a prova que procura aqui, abaixo da prova de que o problema do castor movimentado não é computável.