Re:Gödel's Theorem
by plopilop on Thursday January 31, 2019 @04:43AM
(#19043631)
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.
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.