On 31 May 2015, at 18:38, John Clark wrote:
On Sun, May 31, 2015 Bruno Marchal <marc...@ulb.ac.be> wrote:
>> Other than randomness nobody has ever seen anything in the
physical world that was not computable.
> Physics uses real and complex numbers, and use analysis (which is
second order arithmetic).
That's nice, but other than randomness (an event without a cause)
There are different sort of randomness, most of them capable of
mathematical definition (with and without Church thesis).
"An event without a cause" is a metaphysical or theological notion. In
the type of approach I have develkoped, you would need to make clear
all the assumptions.
nobody has ever seen anything in the physical world that was not
computable.
I can agree with this. Note that if we are machine, we will not been
able to infer if something is not computable, or admit a simple
explanation which elude us.
But computable does not necessarily mean predictable, sometimes the
computation will take as long to perform as it takes the system to
evolve, it's as if even nature doesn't have a shortcut and it must
perform the same calculations you do to figure out what it's going
to do next.
> There are no standard defifinition of computability for the class
of analytical function and sets.
That's nice, but I'm not talking about the class of analytical
function and sets, I'm talking about computing what a physical
system will do,
So you see the problem. Although we can't find anything non-computable
in nature, the physicists still use a highly non computable theories
and ontologies.
This does not mean that there is something non computable, as the
theories on machines also climbs on the non-computable hierarchies, if
only because machines "like" to contemplate those hierarchies.
or in the case of Quantum Mechanics what it will probably do.
> Church thesis only equate a notion of intuitive computability, an
ability to get a result following discrete well determined
elementary digital steps, with computability in some formal system
Only?!
I meant without the need of assuming or using explicit concepts of
physics. This does not mean that the human notion of computability,
like his notion of numbers, have not been influenced by its physical
development, but the notion by themselves does not belongs to the
subject matter of physics. Indeed, theoretical computer science or
recursion theory are branch of mathematical logic, like proof theory
and model theory.
> (lambda calculus, etc.)
And one of the "etc" is a Turing Machine, a device made of matter
that obeys the laws of physics.
Come on. Most textbooks define a Turing machine by a non empty and
finite set of quadruples, where a quadruple is an expression (a finite
sequence) of symbols chosen from q1, q2, .... (called "state" symbol),
S0, S1, S2, ... (tape symbols) and with the L (do on the left), and R
(go on the right symbols). They have to be of the form q_i S_j, S_k,
q_l or q_i S_j, R, q_l or q_i S_j, L, q_l, with the usual intuitive
meaning that if the machine is in state q_i and in front of symbol S_j
then she write S_k (resp. "go to the left of tape", go to to right").
I can say more on Turing machine if people are interested. They have a
nice notion of "instantaneous description", and the notion of piece of
computations that we need to use in the UDA problem can be defined by
finite sequence of instantaneous description brought by a (universal)
Turing machine.
But the key point here is just that a Turing machine is a non empty
finite set of quadruples. It is a precise *finite* mathematical
object. We can enumerate all Turing machine. It is in that context
that Turing discovered the universal Turing machine, an abstract
computer, which is itself a finite set of quadruples. it is a
universal number, when we look at this in another universal system:
Robinson arithmetic.
> It does not require the assumption that there is a physical
universe.
A Turing Machine does assume matter that obeys the laws of physics,
Not at all. What is true, is that the notion of machine has a physical
look, which can help the physicists to get the notion, but the
combinators and lambda calculus, or Post production system, or LISP,
are much less related a priori with the physical. Matiyasevic says
explicitly that although Turing machine can be described in purely
mathematical set-theoretic terminology, he adopts the *convention* (my
emphasis) of describing Turing machine "as though they were physical
devices". It prevents oif too much jargon, in a context where nobody
doubt what we are talking about: indeed matyazevic will shows of
Turing machine can be emulated by diophantine polynomial relations
(hardly physical stuff).
When discussing metaphysics, this pedagogy apparently can lead to
confusion.
and a Turing Machine is equivalent to Lambda Calculus. And in fact
all Lambda Calculus calculations need to be performed on something,
This means that you have not study the papers. Programs need only a
universal program to be executed. That is what universal programs do:
executing or performing Turing machine, or lambda expressions,
combinators' computations. All universal machine can emulate each
others.
It happens that the apparent physical reality can emulate Turing
machine too, and thus all universal numbers. But the big thing is that
all universal machine or number can emulate all the other, and the
notion of "performing" is as much mathematical than the notion of
machine, in this computationalist context.
Computationalism, before reducing conceptually physics to machine
theology, makes very quick clear that the existence of a primitive
physical universe is a strong assumption, without much evidence for
it. It is natural extrapolation to do, but that was the case for "the
earth is flat" or "the sun moves around earth", etc.
and the only something that anyone has ever found that works is
matter that obeys the laws of physics, like a computer or a
biological brain.
Here you mean "happens" in some a priori geographic-historical sense.
It remains open if that sense is reducible in term of simpler senses
(simpler = with less assumptions).
Indeed, with computationalism, that actual geographic-historical sense
is arguably emergent from all the computations, seen from some
internal modality. Eventually we need to postulate only one arbitrary
universal system, and extract the laws of the apparent winners by a
statistics on computations. They have the same computationalist
"measure" in all presentations, so the quantum one, if correct, should
be detectable in the machine's self-reference. And that is the case at
the propositional level, already.
> A priori quantum computation could have been more powerful (in
term of the size of computable functions) than the function
computable with lambda calculus, and this would not have violated
Church thesis,
Even a quantum computer can't produce one of Turing's non-computable
numbers.
We agree on this.
Bruno
A conventional computer can solve any problem that a quantum
computer can just somewhat slower. A lot slower actually, for some
problems a mid sized quantum computer could give you an answer in a
few minutes but a conventional supercomputer would not even be close
to finishing when the sun goes off the main sequence and turns into
a red giant and vaporizes the Earth 10^9 years from now; it would
not even be finished when matter as we know it ceases to exist
because of proton decay 10^40 years from now.
John K Clark
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it,
send an email to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
