Re: Exploiting limitations of Turing machines in Turing tests?

In article <871wbuza1h.fsf@xxxxxxxxxx>, Don Geddis <don@xxxxxxxxxx> wrote:
curt@xxxxxxxx (Curt Welch) wrote on 15 Oct 2007 06:2:
On 14 Ott, 00:58, Don Geddis <d...@xxxxxxxxxx> wrote:
First of all, we know that there exists some Turing Machine that can
correctly answer _any_ halting problem question. Namely, the very
simple Turing Machine that does nothing but detect whether the input is
the halting problem of interest, and then immediately answers "yes" (or
"no"), depending on what the correct answer actually is. And just
loops forever on any other input. (We may not know ourselves whether
the correct TM is the one that answers "yes" [it halts] or "no" [it
doesn't halt], for some input. But since there exists one of each kind
of TM, we do know that whatever the correct answer is, that TM exists.)

So, trivially, within the space of all possible Turing Machines, there
is one that answers correctly for every single input, and loops forever
on any other input.

You were proposing that there exists some finite set of special Turing
Machines, such that if any TM could ever answer a halting problem
question correctly, then at least one of the finite set of TMs would
also answer correctly. I think you're right that if such a set
existed, you could build a huge mondo TM that ran them all in parallel.

But now we've just shown that the huge mondo TM would necessarily be
able to successfully answer _all_ halting problem questions. And we
know from the actual Halting Problem itself that no such TM exists.

Therefore, your hoped-for assumption that a finite set of TMs (which
only answer correctly, or else never halt) could answer any halting
problem that any TM could answer, is false. No such finite set exists.

Ok, this is where you (Don) showed the finite set couldn't exist.

Right.

I still didn't understand the point. I thought you were looking only at
the halting problems which COULD BE solved.

Yes, but you must not have understood my first paragraph above.

_EVERY_ halting problem "can be solved". What is a halting problem, anyway?
It's a description of some Turing Machine, and some input, with the simple
question of "does this Turing Machine halt on this input?"

And what's the correct answer? Well, it's either "yes", or it's "no".

For some given halting problem (TM1 & INPUT1) can you build a new Turing
Machine that recognizes TM1/INPUT1 and outputs "yes"? Sure, that's easy.
Can you build a different Turing Machine that recognizes TM1/INPUT1 and
outputs "no"? Sure, that's easy too. (Both these simple TMs loop forever
on any input except TM1/INPUT1.)

So, _no_matter_whether_ TM1/INPUT1 halts or not, there does exist SOME Turing
Machine that correctly answers the halting question for TM1/INPUT1. (We might
not happen to know which Turing Machine that actually is, but whichever it is,
it certainly exists.)

So: all halting problems can be solved by some Turing Machine. But, on the
other hand, no single Turing Machine can correctly solve them all.

Of all the halting problems that can be solved, does there exist a finite
set to answer all of them? I thought that was the question.

It was the question. And the answer is no, as shown by my proof that you
quoted above.

And from your same logic here, that just translates to the question: is
there a single TM that can correctly answer all halting problem questions
which can be answered?

Sure.

I don't see how to answer that question because I know of no way to define
the set of all halting problems which can be solved.

I hope I've solved that difficulty for you. No individual halting problem is
unsolvable. All halting problems can be solved (by some Turing Machine).

Still beating on this Turing machine lunacy?
Anything else is new under the Sun?

--
The most powerful tool for usenet you have ever heard of.

NewsMaestro v. 4.0.1 Hail Democracy has been released.

Important feature additions and various improvements
and optimizations.

Web page:
http://newsmaestro.sourceforge.net/

Download page:
http://newsmaestro.sourceforge.net/Download_Information.htm

.

Relevant Pages

  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (sci.logic)
  • Re: [PO] Re: Proving a negative is hard
    ... and for these conventions ... > Turing machines with the standard conventions for input/output ... > he agrees that there is no standard Turing Machine program ... > that solves the halting problem, ...
    (sci.logic)
  • Re: [PO] Re: Proving a negative is hard
    ... and for these conventions ... > Turing machines with the standard conventions for input/output ... > he agrees that there is no standard Turing Machine program ... > that solves the halting problem, ...
    (comp.theory)
  • Re: Exploiting limitations of Turing machines in Turing tests?
    ... correctly answer _any_ halting problem question. ... You were proposing that there exists some finite set of special Turing ... able to successfully answer _all_ halting problem questions. ... It's a description of some Turing Machine, and some input, with the simple ...
    (comp.ai.philosophy)
Loading