Re: [PO] Re: Proving a negative is hard
From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 08/22/04
- Next message: Peter Olcott: "Re: Attempt to Refute the Halting Problem's Refutation"
- Previous message: Craig Feinstein: "request for ideas"
- In reply to: Owen Jacobson: "Re: [PO] Re: Proving a negative is hard"
- Next in thread: David C. Ullrich: "Re: [PO] Re: Proving a negative is hard"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sun, 22 Aug 2004 16:16:33 GMT
"Owen Jacobson" <angstrom@lionsanctuary.net> wrote in message news:pan.2004.08.22.07.14.13.987870@lionsanctuary.net...
> On Sun, 22 Aug 2004 04:01:08 +0000, Peter Olcott wrote:
> > There is only one way to make it undecidable. This is a TM such as
> > LoopIfHalts. This TM makes sure that it does whatever the opposite is of
> > what Halt determines. If Halt determines that it will halt, then it goes
> > into an infinite loop. If Halt determines that it will not halt, then it
> > halts. If Halt makes sure that it is never invoked as a part of the
> > execution of another TM, then whenever Halt is provided a TM such as
> > LoopIfHalts, Halt can conclusively determine that it halts. Undecidability
> > has been refuted. There are no more instances that are undecidable.
>
> Are you sure? How are you sure? Nobody has proved that there are no
> other cases that are unanalyzable by Halt(M, x) ==> {0, 1}. Finding a
> single unanalyzable case was sufficient to demonstrate that no TM could be
> Halt(M, x) for all possible values of M and x..
I think that it can now be proven that there can not exist an undecidable case.
In any event it can no longer be claimed to be undecidable now that there is
not evidence to support this conclusion. Since I have correctly refuted this case,
I have disproven the undecidability of the Halting Problem.
> In order to claim that there are no other cases that cannot be analyzed,
> you'll have to provide a proof that this is true.
>
> (I strongly suspect that most programs that contains Halt(M, x) (calls it,
> or contains it inline; they're the same) are unanalyzable by Halt(M, x).)
>
> >> >I have correctly refuted the one case that defined the
> >> >undecidability of the Halting Problem.
> >>
> >> No, you haven't. That one case was about *Turing* machines, with a very
> >> specific convention for inputs and outputs and for coding programs as
> >> inputs. Your examples are all about a *different* convention, and a
This convention was obviously (to me) not intended as a limitation.
Some aspects of the connvention are best kept as limitation. Things
such as the alphabet, ONE, ZERO, SPACE. These are best retained
as limitations because they provide maximum flexability with minimum
complexity. Many other aspects were not intended to be considered
limitations.
In any event, I have yet another refutation of Undecidability that is
even simpler, and does not require any of the features that have
been objected to. I will post this as soon as I thoroughly test its
concept.
> >> *different* model for computation. The standard proof doesn't apply in
> >> your case.
> >
> > The problem is not that the standard proof does not apply in my case.
> > The problem is that the standard proof applies to hypothetical
> > abstractions of Turing Machines, and not actual working hardware.
>
> A Turing machine is a mathematical concept only. No physical machine can
> have a truly infinite amount of storage (tape), yet this is part of the
Except for a very few computations (such as determining every digit of PI)
do not require an infinite amount of memory. So for almost every use of
a Turing Machine the "infinite" memory can simply be viewed as "all that
you need". When it is viewed in these terms suddenly the impossible becomes
practical.
> definition of a Turing machine. The computer on your desk that you're
> reading this post on is not a complete Turing machine. It can run only a
> subset of all possible programs: the subset that can be fit into it's
> memory and disk space. While this is a very large subset, the set of all
> possible Turing machines is not finite.
>
> >> You haven't done any of that work. Only *after* you understand the
> >> relationship is it meaningful to ask whether a theorem about the old
> >> paradigm applies to the new paradigm.
> >>
> >> Of course, nobody (or at least nobody who actually has studied
> >> computability theory) thinks that a new paradigm will make any
> >> difference, because Church's Thesis (which hasn't been proved, but has
> >> a lot of empirical evidence in its favor) implies that the computing
> >> paradigm doesn't make any difference. If the halting problem isn't
> >> solvable with Turing machines, with the usual conventions, then it
> >> isn't solvable for any other paradigm.
> >
> > The "usual conventions" part is the error on your part. If we assumed
> > that the "usual conventions" part was literally true, then every video
> > game completely refutes the Church-Turing thesis. The idea is that the
> > "usual conventions" can be stretched to include video output, rather
> > than strictly adhered to thus refuting Church-Turing.
>
> All of the computations in every video game ever created can be performed
> on Turing machines -- even the computations involved in 3D rendering and
> sound generation. That we see pictures instead of streams of tape symbols
> is a consequence of an agent external to the Turing machine -- your video
> processor and montior -- that can examine the contents of a section of the
> machine's storage -- video memory. Similarly for sound.
This seems to be the right way of looking at this, yet does not refute that the
augmented UTM could not be created as a standard Turing Machine. I
have spent a little time on this, and the augmented UTM could use a
tape for its state transition matrix table.
>
> Furthermore, nobody has ever proven the Church-Turing thesis -- so any
> assertions based on it are necessarily conditional on the thesis' validity.
>
> --
> Some say the Wired doesn't have political borders like the real world,
> but there are far too many nonsense-spouting anarchists or idiots who
> think that pranks are a revolution.
>
- Next message: Peter Olcott: "Re: Attempt to Refute the Halting Problem's Refutation"
- Previous message: Craig Feinstein: "request for ideas"
- In reply to: Owen Jacobson: "Re: [PO] Re: Proving a negative is hard"
- Next in thread: David C. Ullrich: "Re: [PO] Re: Proving a negative is hard"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
