- Rationals are countable. Map each pair to a unique natural number.
- Reals in are uncountable. Assume, for a contradiction that they are countable. Construct a real whose i’th digit is 0 if the i’th digit of the i’th number is odd and 1 otherwise. Then this number has some index t. The t’th digit of the number gives us a contradiction.
- Finite strings are countable, infinite (even binary) strings are uncountable.
- Diagonalization is the proof technique we used for showing sets are uncountable and languages are undecidable.
- Here’s a different proof of the existence of an undecidable language.
- For a binary string , let . In words, it is the shortest string including the description of a Turing machine and an input on which the TM produces the desired string .
- Claim 1. For every integer , there is a string s.t. .
- Define . , the language of incompressible strings is infinite.
- Theorem. The language is undecidable.
- Proof. Suppose is decidable. Then consider the following TM M:
- On input an integer , M scans through each string of length and outputs the lexicographically first string that belongs to .

- Claim 2. Let be the string output by M on input . Then . But . Contradiction for larger than some constant!
- Therefore, our assumption is false and is undecidable.

Advertisements
(function(g,$){if("undefined"!=typeof g.__ATA){
g.__ATA.initAd({collapseEmpty:'after', sectionId:26942, width:300, height:250});
g.__ATA.initAd({collapseEmpty:'after', sectionId:114160, width:300, height:250});
}})(window,jQuery);
var o = document.getElementById('crt-2145631346');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-2145631346",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-2145631346'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}
var o = document.getElementById('crt-1848594847');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-1848594847",collapseContainerIfNotAdblocked:true,"callifnotadblocked": function () {var o = document.getElementById('crt-1848594847'); o.style.setProperty('display','none','important');o.style.setProperty('visbility','hidden','important'); } });
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}