Comment faire valoir que si nous pouvions résoudre le problème de l'arrêt, alors nous pourrions résoudre le castor occupé?

Question

Ceci est l'une des tâches de ma mission. J'ai une simulation de machine de Turing qui permet de simuler un occupé fonction de castor. Je l'ai fait des recherches à prouver ce problème, mais ne comprends toujours pas, donc je suppose que vous pouvez peut-être me aider. Une bonne source pour moi d'aller ou exemple de la façon de faire valoir ce serait bien.

Answer 1

La fonction BB est défini comme étant le nombre maximum d'étapes d'une machine de Turing d'une taille particulière peut mettre en oeuvre et toujours arrêter. (Une autre façon de le mettre est que toutes les machines de Turing x taille se soit arrêté en moins de BB étapes (x), ou courir pour toujours).

En supposant que vous avez une machine de Turing de x complexité, vous pouvez déterminer si elle arrêterait ou non en laissant courir pour BB (x) temps-étapes - si elle n'a pas arrêté alors, par définition, il ne sera.

De même, si vous pouvez résoudre le problème de l'arrêt, vous pouvez évaluer toutes les possibles machines de Turing de taille x, éliminer ceux qui n'arrête pas, et prendre BB (x) pour être le maximum des temps d'exécution des reliquats.

Bien sûr, BB (x) est non calculable - et en fait croît plus rapidement que toute fonction calculable possible, vous pouvez nommer -. Par conséquent, il ne peut même pas être approximée

Answer 2

Vous pouvez trouver la preuve que vous cherchez , ci-dessous la preuve que le problème Beaver Occupé est non calculable.