- 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(){var c=function(){var a=document.getElementById("crt-175345399");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-175345399",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();
(function(){var c=function(){var a=document.getElementById("crt-1385557975");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-1385557975",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();