Stephen Montgomery-Smith wrote: > (I mean, how do you even properly define > 'computable' - Cantor type diagonal arguments are always going to say > any definition is incomplete, like 'the smallest number that cannot be > described in less than 13 words.')
The conundrum you refer to is sometimes called 'the paradox of computability'; if we give a definition of computability it seems we can list all the computable functions (or, rather, all the algorithms computing functions) and diagonalize, getting an intuitively computable function not covered by the definition. The solution to this apparent obstacle is that we can't, in fact, list all computable functions from N to N, and the diagonalization can't be (computably) carried out. There is a story according to which Stephen Kleene become convinced of Chruch's thesis when he realized that one can't computably diagonalize out of the lambda computable functions.
-- Aatu Koskensilta (email@example.com)
"Wovon man nicht sprechen kann, daruber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus