On 18 Mar 2011, at 19:34, meekerdb wrote:

## Advertising

On 3/18/2011 8:12 AM, Bruno Marchal wrote:Hi John,In computer science there is something interesting which can beseen as a critics or as a vindication of what you are saying. Thatthing is the Church thesis, also called Church-Turing thesis, (CT)and which has been proposed independently by Babbage (I haveevidence for that), Emil Post (the first if we forget Babbage),Kleene, Turing, Markov, but not by Church (actually).The thesis has many versions. One version is that ALL computablefunctions can be defined in term of lambda expressions, or in termof Turing machines, or in term of Markov algorithm, or in term ofPost production system, etc. All those versions are provablyequivalent.Such a thesis *seems* to be in opposition with your idea thatcomplete knowledge is impossible. But it is not.The contrary happens. Indeed the thesis concerns only completenesswith respect to computability, and then, as I have already explainon this list, it entails the incompleteness of any effectiveknowability concerning just the world of what machines can do.By "machines" here I assume you mean digital machines/computers.

Yes.

I think this doesn't apply to machines described by real numbers.But of course we think it is unlikely that real number machinesexist and that the reals are just a convenient fiction for dealingwith arbitrarily fine divisions of rationals.

`I don't know. I have not yet find a machine genuinely based on real`

`numbers, but that might make sense. DM assumes I am digitalizable, so`

`that if I am a machine based on the reals, they are not relevant for`

`my identity preservation.`

But there can be a cardinality between the integers and the reals.

You mean that the continuum hypothesis is undecidable in ZF? OK.

I wonder what this implies about computability?

I am not sure there is any.

`Set theories have too much metaphysical baggage which I find more`

`distracting than genuine in the comp frame. But they might be needed`

`to solve complex problem in the future, like the distribution of the`

`primes might need complex analysis. It is hard to tell in advance. The`

`incompleteness phenomenon can be used to predict that the comp theory`

`will split into a huge numbers of variants. It will not stop the war`

`on religious matter! Some will perhaps accept the continuum`

`hypothesis, and others will reject it, leading to different`

`consequences of the comp assumption, but today, the continuum`

`hypothesis is nothing but an example of a an idea which is not used`

`in math or in physics and computer science.`

Bruno

BrentChurch thesis makes it impossible to find *any* complete theoryabout the behavior of machines. I explain this in the firstfootnote of the Plotinus' paper. I can explain if someone ask more.It is proved by a typical use of the (Cantor) diagonalizationprocedure.It vindicates what you say, really. We can sum up this byCompleteness with respect of computability provably entails astrong form of incompleteness for our means of knowability andprovability about machines' possible behavior.This can be proved rigorously in few lines. It is stronger andeasier than Gödel's incompleteness, and it entails Gödel'sincompleteness once we can show that the propositions on thecomputable function can be translated into arithmeticalpropositions (the lengthy tedious part of Gödel's proof).Not only Church thesis makes it possible to think about'everything', but it makes us able to prove our (machine's)limitation about the knowledge about that everything. In any case,this makes us modest, because either CT is wrong and we areincomplete for computability, or CT is true and we are incompleteabout our knowledge about computability, machines, and numbers.Best, Bruno--You received this message because you are subscribed to the GoogleGroups "Everything List" group.To post to this group, send email to everything-list@googlegroups.com.To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com.For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.

http://iridia.ulb.ac.be/~marchal/ -- 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@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.