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

From: Mirek Dobsicek <>
Date: Mon, 11 Feb 2008 17:58:46 +0100

> "But thanks to that crashing, *Church thesis remains consistent*. I
> would just say "An existence of a universal language is not ruled out".
> I am ok with you. Consistent (in math) means basically "not rule out".
> "Formally consistent" means "not formally ruled out", or "not refutable".
> That is:
> "Consistent(p") is the same as "~ Provable(~ p)" " ~" = negation
> like "Provable(p)" is equivalent with "~ Consistent( ~ p)"

All right...

Now, let me just rephrase few points of the key post one more time. I
will try to be picky with wording. Points which are not mentioned - I
fill comfortable with.

1\ There is no language/algorithm/procedure/machine which can
describe/execute all total computable functions.
2\ There exists non-empty set of all machine computable functions
(inevitably includes both total and strict partial functions). Let us
call this set MC (machine computable).
3\ Church himself *defined* the set of so-far-known-computable-functions
as those computable by lambda calculus.
4\ What we use to call a *Church thesis* today says, that MC is in fact
equal to the set of functions computable by lambda calculus.
5\ Church thesis is refutable.

> * * *
> Something else:
> to us verify MM = SII(SII) does crash the system:
> SII(SII) = I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) =
> I(SII)(I(SII)) = SII(SII) = I(SII)(I(SII)) = SII(SII) = ... (crashing).

Working with SK combinators, I had a bit problems with omitted
parenthesis. Also it was not clear to me what is the meaning of eg.
(SKK) since S is expected to take three arguments. What helped me was
the unlambda language (

So here is my crashing sequence (yep, yours is shorter) (I don't expand
the I term to keep it short)

a reference implementation in unlambda:
the ` stands for 'apply' operation, aka left parenthesis.

with a small modification
we can achieve the computer to print uuuuuuuuuuuuu.... in an endless
loop. .u is a special function with a side effect of printing the
character u.


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 Mon Feb 11 2008 - 11:59:04 PST

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