chap limits to computation uncountability before proving that the halting problem is unsolvablewe first prove that not all functions can be implemented as computer program this is so because the number of programs is much smaller than the number of possible functions set is said to be countable (or countably infinite if it is set with infinite membersif every member of the set can be uniquely assigned to positive integer set is said to be uncountable (or uncountably infiniteif it is not possible to assign every member of the set to positive integer to understand what is meant when we say "assigned to positive integer,imagine that there is an infinite row of binslabeled and so on take set and start placing members of the set into binswith at most one member per bin if we can find way to assign all of the members to binsthen the set is countable for exampleconsider the set of positive even integers and so on we can assign an integer to bin / (orif we don' mind skipping some binsthen we can assign even number to bin ithusthe set of even integers is countable this should be no surprisebecause intuitively there are "fewerpositive even integers than there are positive integerseven though both are infinite sets but there are not really any more positive integers than there are positive even integersbecause we can uniquely assign every positive integer to some positive even integer by simply assigning positive integer to positive even integer on the other handthe set of all integers is also countableeven though this set appears to be "biggerthan the set of positive integers this is true because we can assign to positive integer to positive integer - to positive integer to positive integer - to positive integer and so on in generalassign positive integer value to positive integer value iand assign negative integer value - to positive integer value we will never run out of positive integers to assignand we know exactly which positive integer every integer is assigned to because every integer gets an assignmentthe set of integers is countably infinite are the number of programs countable or uncountablea program can be viewed as simply string of characters (including special punctuationspacesand line breakslet us assume that the number of different characters that can appear in program is (using the ascii character setp must be less than but the actual number does not matterif the number of strings is countablethen surely the number of programs is also countable we can assign strings to the bins as follows assign the null string to the first bin nowtake all strings of one characterand assign them to the next bins in "alphabeticor ascii code order nexttake all strings of two charactersand assign them to the next binsagain in ascii code order working from left to right strings of three characters