On 05 Jun 2017, at 04:44, Russell Standish wrote:
On Sun, Jun 04, 2017 at 11:48:23AM -0400, John Clark wrote:
On Sat, Jun 3, 2017 at 9:48 PM, Russell Standish <li...@hpcoders.com.au
>
wrote:
>
That is not the same thing. The largest prime number doesn't
exist, so
there's no answer to find there, but the halting problem always
has an
answer - a program either halts, or it does not.
But that's not the Halting Problem, it's is there a general
way, in a
finite number of steps, to separate all programs into these 3
categories?
1) Programs that will halt and there is a proof they will halt
2) Programs that will not halt and there is a proof they will not
halt
3) Programs that will either halt or will not halt but have no
proof they
will not halt.
Turing gave us the answer to that 80 years ago and it's no. Yes a
program
will either stop or it won't but the Halting Problem isn't about
truth it's
about proof. Mathematicians worry that some important problems,
like the
Goldbach Conjecture, may be in category #3, but if it is we will
never know
that it is. Goldbach could be true but a proof it is true does not
exist,
so a billion years from now, whatever hyper intelligent entities we
will have
evolved into will still be deep in thought looking, unsuccessfully,
for a
proof that it is true and still grinding away at numbers looking,
unsuccessfully, for a counterexample to show it is false.
>
In fact, there are a variety of hypercomputers that can solve the
halting problem in finite time.
It sounds to me like you're talking about one of Bruno's very
silly book
computers that are just ink squiggles on dried wood pulp that are
unable to
calculate 2+2 even if an infinite amount of time were available.
Not at all. Bruno's ontology implicitly assumes such hypercomputers
don't exist.
At the bare level, where only 0, s(0) ... exists. OK.
It is more than we don't need to assume them. We don't have to assume
they do not exist. the assumption is that we can say yes to a doctor
who propose computer for a body/brain. That does not entail we would
die if he gives an hypercomputer, as usually they can emulate all
computers.
The arithmetical truth contains, provably so, all hypercomputers, and
even many "gods/oracles" (not necessary computable).
The computationalist hypothesis assumes only that our brain/body are
computer emulable. That does not entail the non existence of
hypercomputing machinery in the *physical* reality, which on the
contrary should have a non computable first person plural component.
Bruno
It was David Deutsch who initially made the point, with a Hilbert
Hotel computer.
>
Basically, any machine capable of
executing an infinite number of computational steps will be able to
solve the halting problem in finite time.
Right,
executing an infinite number of computations in a finite number of
seconds.
How hard can that be?
There are a number of proposals for for doing so, probably the most
interesting is Malament-Hogarth spacetime, which is a solution to
general relativity that permits such a possibility. It is similar to a
Tipler cyclinder, which is a solution for a time machine that travels
back in time, in the sense that a seemingly impossible physical
situation is allowed by General Relativity.
>
Anything that can be done a Turing Machine can do, if it can't
be done
then a Turing Machine can't do it, and neither can anything
else.
>
That is a thesis about the physical world
Yes.
>
It is quite a strong assumption about reality, and appears to be
true
Yes, but it's no stronger than the assumption perpetual motion
machines
can't be built, or that the Second Law of Thermodynamics is
correct. It is
no stronger than
the assumption everything we know about physics isn't complete
bullshit.
I disagree. There is nothing in conventional physics that rules out
the possibility of a hypercomputer. David Deutsch has proposed a
principle that effectively says "hypercomputers are not possible", but
the fact that hypercomputing solutions of General Relativity exist,
such a principle would mean that something must be up the spout with
that.
But then, we know that QM is incompatible with GR, and I strongly
suspect it is GR that will need modification, so it doesn't bother me
if this is just something else that needs changing in Einstein's
theory. But it may well be that the physical CT thesis is itself only
some classical approximation. We just don't know at this stage.
--
----------------------------------------------------------------------------
Dr Russell Standish Phone 0425 253119 (mobile)
Principal, High Performance Coders
Visiting Senior Research Fellow hpco...@hpcoders.com.au
Economics, Kingston University http://www.hpcoders.com.au
----------------------------------------------------------------------------
--
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 https://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 https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.