abo wrote: > Aatu Koskensilta wrote: > >>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 was using the term rather loosely, to mean that it might seem that in some highly idealized sense we, the actual human beings, should be able to write down all the algorithms in succession.
> 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.
Yes, that's the point.
-- Aatu Koskensilta (firstname.lastname@example.org)
"Wovon man nicht sprechen kann, daruber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus