Problem:
Show that the set of incompressible strings contains no infinite subset that is Turing recognizable.
Short proof:
If such an infinite subset exists, we can compress those strings using a Turing enumerator.
Proof:
If such an infinite subset exists, we build an enumerator of them. By the recursion theorem, we can build a Turing machine that enumerate the strings that infinite subset and stop on the first string that is larger than the representation of itself.
Such a machine must eventually halt because of the set must have a string with length larger than this finite machine.
Show that the set of incompressible strings contains no infinite subset that is Turing recognizable.
Short proof:
If such an infinite subset exists, we can compress those strings using a Turing enumerator.
Proof:
If such an infinite subset exists, we build an enumerator of them. By the recursion theorem, we can build a Turing machine that enumerate the strings that infinite subset and stop on the first string that is larger than the representation of itself.
Such a machine must eventually halt because of the set must have a string with length larger than this finite machine.
No comments :
Post a Comment