online advertising

Wednesday, January 4, 2017

Show that the set of incompressible strings contains no infinite subset that is Turing recognizable.

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.

No comments :

Post a Comment