Re: Yet another Attempt at Disproving the Halting Problem

From: Kent Paul Dolan (xanthian_at_well.com)
Date: 07/30/04 

Date: Fri, 30 Jul 2004 14:29:17 +0000 (UTC)

"Peter Olcott" <olcott@worldnet.att.net> wrote:

> We can have a separate memory space.

Well, no, you can't.

The whole point of discussing the solution of the
halting problem in terms of the abstraction called
"a Turing machine", is to remove extrania from the
discussion.

Unneeded extrania only allow for the confused
hand-waving of dunces to be amplified by irrelevant
complexity, an amplification you have been at great
pains to demonstrate for the audience with your
refuge in arguments about "the operating system",
"weird versions" and all.

A Turning machine has _one_ memory space to which
the machine itself has access, its tape.

It does not, for example have the capability to
introspect upon, or to modify, its own program, only
to introspect upon, or modify, a copy of that
program made onto its tape.

[Thus, it is not itself "a stored program computer";
however, it can perfectly emulate one by treating
part of the data on the tape as if IT were a stored
program, to be interpreted by the fixed, immutable
program which is the real Turing machine program.]

Modifications to the version on the tape have no
impact on the program which is running _as_ the
Turing machine; that version is immutable (though
stateful) and is also invisible to itself.

Moreover the Turing machine has no way whatever to
know whether the version of its immutable program
sitting as mutable data on the tape is a true copy
of itself, so taking refuge in the results of
introspection cannot exist as part of your "proof"
mechanism, where the subject of your proof is
"Turing machines as conceptually formally
implemented", the very subject of the "long-ago
proved beyond your ability to refute" disproof of
the solvability of the Halting Problem.

xanthian.

And note that even this is _much_ more complex than
the actual _formal_ definition of a Turing machine.

A Turning machine is defined formally simply as a
tuple of heterogeneous mathematical entities, using
the concepts and notations of set theory.

There are five of those entities, if I recall
correctly.

Hmm. Nope, I didn't, I sometimes suffer from some
weird compulsion, one you wouldn't understand, to
check my work; there are seven of them:

http://www.wordiq.com/definition/Turing_machine

But, don't go looking at that formal definition,
it won't help you a bit.

If the informal definition (available on the same
web page) is so obviously beyond your comprehension,
the formal definition would just look to you like
some APL program.

Worse yet, the one at the cited URL is more
confusing to you than that.

It uses the fairly standard 'Net convention of
writing complex mathematical statements using
Knuth's TeX expressions _as if_ everyone reading
them knows exactly how they would be rendered _if
only_ HTML 4.01 were TeX-compliant as well.

That is done because that choice is significantly
easier than writing the statements in the math
notation format HTML _does_ support, and then
pretending that browser authors will have correctly
implemented that format, a pipe dream long in the
dreaming but short in the realizing. 

-- 
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG

Relevant Pages

  • Re: Yet another Attempt at Disproving the Halting Problem
    ... "a Turing machine", is to remove extrania from the ... its tape. ... the solvability of the Halting Problem. ... But, don't go looking at that formal definition, ...
    (sci.logic)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... > There does not a exist Turing Machine H, such that for all M in TM ... > the tape of H. ... write and om is the motion for the output tape. ... The "halting problem" takes a machine M and input x and decides ...
    (comp.theory)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... > There does not a exist Turing Machine H, such that for all M in TM ... > the tape of H. ... write and om is the motion for the output tape. ... The "halting problem" takes a machine M and input x and decides ...
    (sci.logic)
  • Re: [QUIZ] The Turing Machine (#162)
    ... tape = tape ... The Turing Machine ... The three rules of Ruby Quiz 2: ... An infinite tape of memory cells that can hold one character ...
    (comp.lang.ruby)
  • Re: Symbol Grounding Problem
    ... on the tape before execution begins. ... But Windows is interactive, ... can a Turing machine run windows? ... PC can run the equivalent of an oracle, ...
    (comp.ai.philosophy)