Re: Key Post 1, toward Church Thesis and Lobian machine

From: Mirek Dobsicek <>
Date: Wed, 05 Dec 2007 23:08:34 +0100

Hi Bruno,

thank you for your post. I read it a couple of times in order to more or
less grasp it, but it worth it. I have some questions...

> Suppose there is a secure universal machine M. The set of expressions
> it can compute provide a secure universal language L. That set is not
> only enumerable (given that it is a subset of an enumerable set) but
> above all, it can be enumerated effectively (by the "ashole").

What do you mean here by effectively? I understand it as you just want
to emphasize that the set is really enumerable.

> So, as you know, Church did *define* a computable function by a
> function computable by a lambda expression, in its conversion calculus.

Why do you introduce here the term 'lambda expression'? I'm asking this
because in the sequel you work just with 'a well specified language
which is promised to be universal' and you prove that such a promise is
not ruled out.
I do not see how you reached the conlusion:
"But thanks to that crashing, *Church thesis remains consistent*. I
would just say "An existence of a universal language is not ruled out".

> Each expression like that denotes now either a computable function from
> N to N, or as we have to expect something else. And we have to expect
> they are no computable means to distinguish which U_i represents
> functions from N to N, and which represents the other beast.

Can I say that the other beasts are only and only infinite loops? I
assume that the machine cannot destroy itself, so it either stops after
computing a computable function or enters some silly loop.

> Indeed, the diagonalisation above, where now the f_i are the *partial
> computable functions*, meaning they are from N to N, OR from a subset
> of N to N, does no more lead to a contradiction.

I have a problem with this paragraph, could you please write more on
this? I understand to partial computable functions as to functions which
are not *defined* for every possible input (total functions are defined
for all inputs, in my limited understanding). Do you say in that
paragraph that beasts are only and only these partial functions?

Huh, now what do I mean by *defined* ... maybe I should say 'which are
not computable for every possible input'. I am really lost here...

And my last question, consider the profound function
f such that f(n) = 1 if there is a sequence of n consecutive fives in
the decimal expansion of PI, and f(n) = 0 otherwise

Is this an example of a partial computable function? Or is this function
as such already considered as un-computable function?

With best regards,

You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to
To unsubscribe from this group, send email to
For more options, visit this group at
Received on Wed Dec 05 2007 - 17:08:40 PST

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:14 PST