Homework Soursea Show that any infinite set of MINTM is not Turingrecogniza
a) Show that any infinite set of MINTM is not Turing-recognizable.
b) Show that if A?T B and B?T C then A?T C.
c) Show that the set of incompressible strings is undecidable
Please post handwritten work instead of something you googled, copied and pasted
Solution
The second question is the easier one, we can just pick any string ? in the infinite Turing recognizable language S, and let S?=S?{?}. Then you should be able to construct a TM that recognizes S? from the recognizer R for S.
The normal proof for the first question is trickier, relying on two facts:
So you start with S, which must have an enumerator E that prints out, one by one, the strings in S in some order, which may include repeats. What you have to do is construct a lexicographic enumerator using E as a subroutine. It doesn\'t have to print out everything in S, just a subset of course, the trick is to ensure that the ones it prints are in lexicographic order. As noted Jeremy West in the comments, we must also ensure that the subset is infinite, this is easy enough, just not to be forgotten.
The total amount of Crypti in existence will be 100 Million. The pre-sale will The total amount of Crypti in existence will be 100 Million. The pre-sale will last 30 days and we will accept Bitcoin only.
I would like to see a proof or a sketch of a proof that the set of incompressible strings is undecidable.
Definition: Let x be a string, we say that x is c-compressible if K(x) ? |x|-c. If x is not c-compressible, we say that x is incompressible by c. K(x) represents the Kolmogorov complexity of a binary string x.
Theorem: incompressible strings of every length exist.
Proof: The number of binary strings of length n is 2n, but there exist ?i=0n?12i=2n-1 descriptions of lengths that is less than n. Since each description describes at most one string then there is at least one string of length n that is incompressible.
From here I feel it is natural to ask whether or not the set of incompressible strings is decidable, the answer is no, but I would like to see the justification via a proof or proof sketch.
Edit: I would like to add I am already familiar/comfortable with the proof that Kolmogorov complexity is uncomputable.
