Re: The Modified Halting Problem, Take ??? .

In sci.logic, Stephen Harris
<cyberguard-1048@xxxxxxxxx>
wrote
on Tue, 24 Oct 2006 07:18:15 GMT
<X6j%g.23343$7I1.9762@xxxxxxxxxxxxxxxxxxxxxxxxxx>:
The Ghost In The Machine wrote:
I. The Claim.


Granted, H() may not be a computable function, for the heat
death of the Universe may occur first. But mathematicians
don't have a problem with that, and compute sums such as
sum(i=1,+oo) (1/2^i) all the time -- though the methods are
usually a little smarter than



So...anything obvious I've missed in all of the above?


I don't know as much about this as you do,

It's been awhile. :-) I'm a software engineer by profession, and don't
really do much more than dabble in the stuff.

and only feel
qualified to comment on one small section which I think
is important because I don't think the OP knows what a TM is.

Peter O. might not know what a TM (Turing Machine) is.
I'm aware of a TM, at least at a general level; it is
an infinite-tape machine with a finite state set and
a transition function which maps (s, a) to ({L,R}, s', a'),
where s,s' are in a finite set S and a,a' are in a
finite set A, and L and R are abstract tokens, one associated with
a head movement to the left, the other associated with a movement to the
right. (s and s' need not be distinct; ditto for a
and a'.) There are a number of variants of Turing machine,
all variations on a theme; one of the more elegant ones has an
infinite bidirectional tape and a half-infinite bidirectional tape,
intended to be used as a stack. (A partially-modeled machine is
actually used in many auto-generated parsers; of course the tape
is not infinite and tape motion is generally forward, for the
sake of efficiency.)

I prefer indefinite-register machines, but those are
also equivalent to a Turing machine (one can replace
the registers with a single Turing tape and the program
becomes a state set and transition function, or simulate
a Turing machine with a fairly simple program on an
indefinite-register machine).


A TM is an abstract device. It has no physical constraints
such as time or storage. So heat death is not a factor (you
may been exercising your sense of humor)

I was. :-)

which would make
a computation intractable. An algorithm has some definitional
constraints such as finiteness and coming to an end which do
not apply to TMs. Pi is defined as computable even though its
expression has an infinite number of digits. A Turing machine
can compute the digits of Pi without ever halting (although
individual digits of Pi are calculated finitely in an unending
series of steps). In this case one knows the program will
continue to run because it is known that Pi has infinite digits.
Knuth uses 'computational method' to describe something which
is just like an algorithm but doesn't have the termination rule.

Which is different than the Wiki Halting Problem short description:
"Given a description of a program and a finite input, decide
whether the program finishes running or will run forever,
given that input."

So the potentially infinite turing tape eliminates concerns
about a program halting due to inadequate resources (time)
which might be a factor for a physical computer, are eliminated
in the theoretical discussion of TMs. Also, all that is listable
is not computable, and all that is computable is not listable.

It does get a little complicated. The Halting Problem
is a little literal as well, since given any alleged
algorithm, one constructs a function (or a machine)
that cannot be answered correctly *by that algorithm*
(some other algorithm might get it, but that algorithm
has his own demon-spawn which fails *it*).


Regards,
Stephen

--
#191, ewill3@xxxxxxxxxxxxx
Insert random misquote here.

--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages

  • Re: Turing machines, quantum computers, and alephs
    ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
    (sci.math)
  • Re: Turing machines, quantum computers, and alephs
    ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
    (sci.math)
  • Re: turing completeness
    ... The tape doesn't have to be "infinite", ... Turing machine on a physical computer" you are wrong. ... Formalism was David Hilbert's movement, that claimed that programming, ...
    (comp.programming)
Quantcast