Aatu Koskensilta wrote: > 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. > > --
Are you using "list" to mean there exists a *computable* function with domain N? I always thought that "list" meant there exists a function with domain N. In my sense there is in fact a list of the computable functions, but because because the listing function is itself not computable, the diagonalization from the list can't be computably carried out.