On 1/10/2012 17:48, Bruno Marchal wrote:
On 10 Jan 2012, at 12:58, acw wrote:
On 1/10/2012 12:03, Bruno Marchal wrote:
On 09 Jan 2012, at 19:36, acw wrote:
To put it more simply: if Church Turing Thesis(CTT) is correct,
mathematics is the same for any system or being you can imagine.
I am not sure why. "Sigma_1 arithmetic" would be the same; but higher
mathematics (set theory, analysis) might still be different.
If it's wrong, maybe stuff like concrete infinities, hypercomputation
and infinite minds could exist and that would falsify COMP, however
there is zero evidence for any of that being possible.
Not sure, if CT is wrong, there would be finite machines, working in
finite time, with well defined instructions, which would be NOT Turing
emulable. Hypercomputation and infinite (human) minds would contradict
comp, not CT. On the contrary, they need CT to claim that they compute
more than any programmable machines. CT is part of comp, but comp
is not
part of CT.
Beyond this, I agree with your reply to Craig.
In that response I was using CT in the more unrestricted form: all
effectively computable functions are Turing-computable.
I understand, but that is confusing. David Deutsch and many physicists
are a bit responsible of that confusion, by attempting to have a notion
of "effectivity" relying on physics. The original statement of Church,
Turing, Markov, Post, ... concerns only the intuitively human computable
functions, or the functions computable by finitary means. It asserts
that the class of such intuitively computable functions is the same as
the class of functions computable by some Turing machine (or by the
unique universal Turing machine). Such a notion is a priori completely
independent of the notion of computable by physical means.
Yes, with the usual notion of Turing-computable, you don't really need
more than arithmetic.
It might be a bit stronger than the usual equivalency proofs between a
very wide range of models of computation (Turing machines, Abacus/PA
machines, (primitive) recursive functions (+minimization), all kinds
of more "current" models of computation, languages and so on).
Yes. I even suspect that CT makes the class of functions computable by
physics greater than the class of Church.
That could be possible, but more evidence is needed for this(beyond
the random oracle). I also wonder 2 other things: 1) would we be able
to really know if we find ourselves in such a world (I'm leaning
toward unlikely, but I'm agnostic about this) 2) would someone
performing my experiment(described in another message), lose the
ability to find himself in such a world (I'm leaning toward 'no, if
it's possible now, it should still be possible').
If hypercomputation was actually possible that would mean that strong
variant of CT would be false, because there would be something
effectively computable that wasn't computable by a Turing machine.
OK.
In a way, that strong form of CT might already be false with comp,
only in the 1p sense as you get a free random oracle as well as always
staying consistent(and 'alive'), but it's not false in the 3p view...
Yes. Comp makes physics a first person plural reality, and a priori we
might be able to exploit the first plural indeterminacy to compute more
function, like we know already that we have more "processes", like that
free random oracle. The empirical fact that quantum computer does not
violate CT can make us doubt about this.
In the third person, there's no need to consider more than UD, which
seems to place some limits on what is possible, but in the first
person, the possibilities are more plentiful (if COMP).
Also, I do wonder if the same universality that is present in the
current CT would be present in hypercomputation (if one were to assume
it would be possible)
Yes, at least for many type of hypercomputation, notably of the form of
computability with some oracle.
- would it even retain CT's current "immunity" from diagonalization?
Yes. Actually the immunity of the class of computable functions entails
the immunity of the class of computable functions with oracle. So the
consistency of CT entails the consistency of some super-CT for larger
class. But I doubt that there is a super-CT for the class of functions
computable by physical means. I am a bit agnostic on that.
OK, although this doesn't seem trivial to me.
As for the mathematical truth part, I mostly meant that from the
perspective of a computable machine talking about axiomatic systems -
as it is computable, the same machine (theorem prover) would always
yield the same results in all possible worlds(or shared dreams).
I see here why you have some problem with AUDA (and logic). CT = the
notion of computability is absolute. But provability is not absolute at
all. Even with CT, different machine talking or using different
axiomatic system will obtain different theorems.
In fact this is even an easy (one diagonalization) consequence of CT,
although Gödel's original proof does not use CT. provability, nor
definability is not immune for diagonalization. Different machines
proves different theorems.
If questions(axiomatic system being looked into) are different,
results can be different too, but if the questions (and inference
steps) are the same, shouldn't the result always be the same? This
would follow from CTT implementing a theorem prover.
Although with my incomplete understanding of the AUDA, and I may be
wrong about this, it appeared to me that it might be possible for a
machine to get more and more of the truth given the consistency
constraint.
That's right both PA + con(PA) and PA + ~con(PA) proves more true
arithmetical theorems than PA.
And PA + con(PA + con(PA + con (PA + con PA)) will proves even more
theorems. The same with the negation of those consistency.
I do wonder what kind of interesting theorems would result from those.
Note that the theory PA* = PA* + con(PA*), which can be defined finitely
by the use of the Kleene recursion fixed point proves ALL the true
propositions of arithmetic!!! Unfortunately it proves also all false
propositions of arithmetic. This follows easily by the second theorem of
Gödel, because such a theory can prove its own consistency given that
(con "itself") is an axiom, and by Gödel II, it is inconsistent.
PA* is the one which claims its on consistency as a theorem? It would
be inconsistent in that case, and unfortunately, even if it shows some
new truths, we lose the ability of telling true from false, making it
a bit useless once one starts making inferences from false statements.
But, yes, once you have a consistent machine, you can extend its
provability ability on the whole constructive transfinite.
How come? PA being able to encode a theorem prover for ZFC, wouldn't
mean PA believes in the truth of ZFC(or some other set theory)? Or did
I misunderstand something here. Maybe you should recommend me some
book or paper to read that would explain this to me.
As for higher math, such as set theories: do they have a model and are
they consistent? (that's an open question) If some forms close to
Cantor's paradise are accepted in the ontology, wouldn't that risk
potentially falsifying COMP?
Trivially. You can refute comp in the theory ZF + ~comp (accepting some
formalization of comp in set theory).
With that question I was more concerned about the number of entities
appearing in the theory and that the possibility of concrete
infinities appearing in the physics and thus leading to possible
worlds where brains implementations have with concrete infinities =
lack of substitution level.
Remember that, like consistency, (~ probable comp) is consistent with
comp. If comp is true, like consistency, it is not provable, and so you
can add (~ provable comp), or (con ~comp) to the comp theory of
everything (arithmetic) without getting an inconsistency with comp. Of
course you should not add ~comp to comp at the same (meta)level. You
will get a contradiction.
I've always wondered about one thing: if there are solid evidences for
COMP being true(in the sense of no evidence about it being false being
found, its predictions confirmed by observation and so on), wouldn't
that warrant a belief in it? It would be religious belief in a way,
like belief in the consistency of PA or some others belief in God or
primitive matter or reality or particular physical laws or whatever
(some may be true, other may be false, but one must have some
assumptions if they have to bet on something).
In another way, a conscious machine can always doubt that it's a
machine and this doubt would not make it inconsistent.
Likewise, as above, the theory PA + (PA is inconsistent) is consistent.
You can prove, in it, that the false is provable, but you cannot prove,
in it, the false. Bf -> f is not a theorem (Bf -> f) = ~Bf =
consistency.
I always found that as a non-intuitive consequence of Godel's theorems.
PA doesn't contains a proof of its own consistency, if it's consistent
(it is inconsistent if it does contain it).
On the other hand, in a stronger theory, which shows PA consistency
(for example ZFC), wouldn't PA + (PA is inconsistent) be inconsistent?
Or to put it different, wouldn't it lack a model (because 'PA is
inconsistent' would be false, despite not being provable within PA
itself)?
Maybe it could even be generalized to adding a sentence which could be
false, but from which nothing false could be proven within some
axiomatic system.
I hope that some of these ideas will be clearer to me after I'm done
reading those books on logic and provability.
I can see many reasons why a particular machine/system would want to
talk about such higher math, but I'm not sure how it could end up with
different discourses/truths if the machine('s body) is computable.
Here there is a difficulty, and many people get it wrong. There is a
frequent error in logic which mirrors very well Searles error in his
chinese room argument. With comp I can certainly simulate Einstein's
brain, but that fact does not transform me into Einstein. If someone
asks me a complex question about relativity, I might be able to answer
by simulating what Einstein would respond, but I might still not have a
clue about what the meaning of Einstein's answer. In fact I would just
make it possible for Einstein to answer the question. Not me.
Like wise, a quasi debilitating arithmetical theorem system like
Robinson Arithmetic, which cannot prove x+y = y+x, for example, is still
Turing universal, and as such can imitate PA perfectly through its
provability abilities. That is, RA is able to prove that PA can prove
x+y=y+x. But RA has not the power to be convinced by that PA's proof,
like I can simulate Einstein without having the gift to understand any
words by him.
RA can simulate PA and ZF, and even ZF+k (which can prove the
consistency of ZF), but this does not give to RA the *provability* power
of PA, ZF or ZF+k.
PA can prove that ZF can prove the consistency of PA, but PA can still
not prove the consistency of PA.
I don't think I said that PA can take other system's truths as their
own, even if it can simulate other systems, it cannot believe they are
true, and if it could, it no longer would be PA, but some other system.
What I was talking about was a bit different, formal systems can be
simulated by some UTM, thus while the UTM wouldn't "be" the system (in
the same way that in COMP, a brain could allow a mind to manifest
relatively to some other observers, but it wouldn't be that mind),
given the same questions asked to some particular Turing-emulable
system, the answers will always be the same. That of course doesn't
mean that PA can take ZFC truths as its own - they are not provable in
PA.
In another way, the totality of possible discourses should be present
within PA, but that doesn't mean PA can take them as its truths.
There's another problem here: not all formal systems will be
consistent or have models, but unless we have proofs of their
inconsistency, we will never know.
Some of this confusion might be because, we as humans, sometimes take
other people or system's beliefs as our own, even if doing so is not
always rational, but despite that this increases the risk of being
wrong, it also lets us get to a lot more truth.
I can see it discovering the independence of certain axioms (for
example the axiom of choice or the continuum hypothesis), but wouldn't
all the math that it can /talk/ about be the same? The machine would
have to assume some axioms and reason from there.
Yes. And with different axioms you get different provability aptitudes.
Once a machine can prove all true arithmetical sigma_1 sentences (with
the shape ExP(x) with P decidable) she is universal, with respect to
*computability. You can add as many axioms you want, the machine will
not *compute* more functions. But adding axioms will always lead the
machine into proving more *theorems*.
In AUDA, "belief" is modeled by provability (not computability), and
then knowledge is defined in the usual classical (Theaetetus) ways. All
beliefs of the correct machines will obeys to the same self-referential
logic, but all belief-content will differ from a machine to a different
machine. PA and ZF have the same self-referential logics, but they have
quite different belief, even restricted on the numbers.
For example ZF proves more arithmetical truth than PA. ZFC and ZF+(~C)
proves exactly the same theorem in arithmetic, despite they proves quite
different theorem about sets (so arithmetic is deeply independent of the
axiom of choice). ZF+k (= ZF + it exists an inaccessible cardinal)
proves *much more* arithmetical theorem than ZF.
To sum up:
Computability is an absolute notion.
Provability is a relative notion.
I think we're mostly in agreement here, beliefs (what's provable) will
differ per machine, and with adding more axioms, more beliefs are
possible.
There can be many 'believers'(axiomatic systems), but all of them can
be implemented by the same base(their "body", some theorem prover
implemented by some UTM).
However, I would like to know what the many more arithmetical theorems
ZF(and some of its extensions) that proves are. The only ones I'm
familiar with are the type of PA's consistency and Goodstein's theorem
as well as similar results about the fact that some sequences
terminate/halt.
BTW, acw, you might try to write a shorter and clearer version of your
joining post argument. It is hard to follow. If not, I might take much
more time.
Bruno
I think I talked about too many different things in that post, not all
directly relevant to the argument (although relevant when trying to
consider as many consequences as possible of that experiment). If some
parts are unclear, feel free to ask in that thread. The general
outline of what I talked about in the part you have yet to comment on:
a generalized form of the experiment the main character from
"Permutation City" novel performed is described in detail(assuming
COMP), a possible explanation for why it might not actually be useless
to perform such an experiment and why it might be a good practical
test for verifying the consequences described in the UDA, various
variations/factors/practicalities of that experiment are discussed
(with goals such as reducing white rabbits, among a few others), some
not directly relevant to the argument and at the end I tried to see if
the notion of observer can be better defined and tried to show that
the notion of "generalized brain" might not always be an appropriate
way to talk about an observer. That post was mostly meant to be
exploratory and I hoped the ensuing discussion would lead to 2 things:
1) assessing the viability of that experiment if COMP is assumed AND
2) reaching a better definition of the notion of observer.
OK. This I think I understood this, but your style is not easy, and it
might be useful, even within your goal, to work on a clearer and shorter
version, with shorter sentences, without any digression, with clear
section and subsection, so as to invite most people (including me) to
grasp it, or to find a flaw, and this in reasonable time. In particular
I fail to see the point of discussing the use of different universal
systems like you did with the Cellular Automata (CA).
Bruno
http://iridia.ulb.ac.be/~marchal/
I will consider rewriting it if the time allows. The original idea as
presented in that book, had a CA as their "primary physics", so I
tried to show the difference between my experiment and the experiment
in the book.
If one assumes COMP, there is no longer a need for choosing any
particular physical system, such as a CA. I then went on to say that
if a 'physical CA' is chosen, there are many practical problems that
could occur, both a decrease in stability(white rabbits, jumpyness),
as well as many problems for those living with the system
(speed-of-light limit and most social problems present in our physical
world).
I think it could only be 100% stable if the (mind's) substitution
level is exactly at the CA level, which was not the case in the book.
Instead of such a "primary physics", I just choose an easy to
design/program Turing-equivalent machine (such as something based on a
PA machine), which implements a message-passing operating
system/scheduler on top of it. I argue that the careful use of a
random oracle should reduce the chance of white-rabbits and increase
the overall world's stability(1p experiences not being too jumpy), but
I still don't know to what degree this would be sufficient (oracle
implemented by dovetailing or leaving "undefined"). I tried to
consider how the choice of OS and observer's implementation could
affect the world's stability(1p).
As a thought experiment, I could have stopped there, but I decided to
consider more practical details as well, because if one day there will
be a computationalist doctor to say yes to and one wants to perform
such an experiment, they better have all their details right,
otherwise after performing the experiment, their future 1p experiences
might not be very pleasant.
