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

From: Mirek Dobsicek <m.dobsicek.domain.name.hidden>
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

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

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

with a small modification
```sii``si``s`k.ui
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.

Best,
Mirek

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
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