The number of functions (or rather programs) is countable though, as we can think of them as Turing machine. A Turing machine is a set of the form (states, tran

The number of functions (or rather programs) is countable though, as we can think of them as Turing machine. A Turing machine is a set of the form (states, transitions). Given that a Turing machine has finite number states and transitions, there are countably many such machines. So indeed, we reach a contradiction, but the hypothesis was : > To make things even easier, we can just throw out programs that loop infinitely or don’t return a 1 or a 0 so the contradiction tells us that \bar f is not in this set. More specifically, \bar f may loop infinitely at some point, I guess it does loop when you feed \bar f to itself.