Re: On The Proper Formulation Of The Halting Problem

From: |-|erc (gotch_at_beauty.com)
Date: 07/27/04 

Date: Tue, 27 Jul 2004 01:40:36 GMT

"The Ghost In The Machine" <ewill@aurigae.athghost7038suus.net> wrote in
> In sci.logic, |-|erc
> <gotch@beauty.com>
> wrote
> on Mon, 26 Jul 2004 10:55:40 GMT
> <Mq5Nc.17405$K53.9866@news-server.bigpond.net.au>:
> > "The Ghost In The Machine" <ewill@aurigae.athghost7038suus.net> wrote
> >> At the risk of beating this deep into the ground (where
> >> it probably should be anyway, in a nice little pine box
> >> with flowers, a eulogy, and a properly mounted gravestone;
> >> blinking colored lights and sign are optional), the usual
> >> formulation of the Halting Problem is more or less along
> >> the following lines:
> >>
> >> Let m be a machine and i its input tape. Can another machine
> >> h be constructed such that it can predict whether m(i) will
> >> halt?
> >>
> >> (There are a couple of minor technical problems with this
> >> formulation, mostly since I'm not sure classical Turing
> >> Machines have halting states, and the proper encoding of
> >> the machine descriptor and the input alphabet; we'll elide
> >> them for now.)
> >>
> >> The standard disproof is to take the result of h and
> >> construct a machine w such that, if h predicts w(i)
> >> will halt, w(i) will loop, and vice versa. (w does
> >> this by mangling its input i in a precise fashion,
> >> then running h's states and transitions, and then
> >> becoming pathological.)
> >>
> >> Peter Olcott is apparently of the opinion that, if
> >> one forbids h from returning anything to w, then one
> >> has somehow solved a detail of the halting problem by
> >> preventing the disproof of h's existence from closing
> >> the loop.
> >>
> >> IMO, a stranger position is hard to find, although
> >> one can try the following, without success, to disrupt
> >> the proof:
> >>
> >> [1] extend the machine. Basically, this changes the specification
> >> of a machine m. It also changes h and w.
> >> [2] encrypt h's output. All this does is make w's job harder, but
> >> w can still do the job -- it just takes a lot longer.
> >> If the encryption is strong enough, the Universe might die first.
> >> [3] randomize the bitflip. This very strange position basically
> >> makes h's output useless, as it XORs it with a random value
> >> which can be read by no other program. (If the bitflip is
> >> available to the other program, see [1] or [2]. For purposes
> >> of this discussion humans are equivalent to programs. ;-)
> >> More precisely, if a human can read the bitflip, the machine
> >> can be modified (see [1]) to make its output available to
> >> another program as well.)
> >> [4] use a different machine type for h. Since all machines are
> >> essentially mappable this doesn't do much. (Peter Olcott's
> >> formulation of this is that h has a "side effect"; however,
> >> that "side effect" is not specified. If the side effect is
> >> an indicator light or another output tape it's basically a
> >> machine change [1].)
> >> [5] change the problem (strawman). Instead of specifying h as
> >> predicting whether m(i) will halt, specify additional inputs
> >> such as n, and ask whether m(i) will halt within n cycles.
> >> The trouble with that particular position is that that's
> >> ridiculously easy: just emulate m(i) for n cycles, then see
> >> whether the machine's in its halt state.
> >>
> >> Did I miss any? :-) Regardless of all this, the original Halting
> >> Proof remains unmolested: h is impossible. Oh, h is possible
> >> if one severely restricts the class of machines m (one possibility
> >> is to restrict the number of iterations ([5]); another is to
> >> forbid arbitrary mu-loops) but for a sufficiently general
> >> class of machines, w twists h's output enough to make h malfunction.
> >>
> >
> >
> > The only avenue we have is h is possible if one severely restricts the class of machines m,
> > we have a program H that contains an identifier string, like 3983748 or 'thisishalt'.
>
> H is not unique; a series of trivial transformations can generate a whole class of
> machines H.
>
> In any program, if I switch metaphors for a bit, one can switch:
>
> MOV #0, R0
>
> to
>
> SUB R0, R0
>
> for example; this is one of many transformations that one can apply to a program P
> to generate an equivalent program P' whose sole difference may be that it runs
> more quickly or more slowly.
>
> The explicit construction of H may be required for further analysis along these lines.
> It would be interesting for H to contain its own self-identifier, but for most
> non-compressing encoding schemes that would mean that H contains a self-identifier
> shorter than H's self-identifier -- a contradiction. Therefore, the machine encoding
> would have to be compressing, and even then one has a problem, as the self-identifier
> completely specifies the machine, and therefore, from what very little I know about
> information theory, H contains more information than its specification and also contains
> its own specification!
>
> While it is possible for a program to print out itself (in C, anyway), I think in the
> general case that H won't be able to usefully contain its own identifier, and even if
> it could, there are many trivial variants of H which it would have to check for.
>
> >
> > Then H can identify M with a substring match for 'thisishalt' as having a self reference.
> >
> > H outputs "don't know" for this *small* class of programs.
> >
> > Your argument now becomes, m uses a function h' that is equivalent to H but doesn't
> > contain the string 'thisishalt' in its encoding.... h' <=/=> H therefore its impossible too.
> >
> > To prove h' exists use encryption on H and a UTM to parse e(H) - the string EH, such that
> > m contains the function UTM(c(EH)) instead of H, where 'thisishalt' is scrambled
> > atleast until UTM is partially run, c is for crack, e is for encrypt. c(e(X)) = X.
> >
> > What's to stop a better mechanism than using an identifier string, to detect usage of any equivalent
> > function to H?
>
> Go ahead and build such an H, then. Use any Universe you desire: Turing machines,
> infinite-length infinite-register machines, LISP tokens, etc.
>
> >
> >= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
> >
> > Another scenerio. Can we universally detect a number is prime in poly time?
>
> O(N^(1/2) * (log N)^2), if I'm not mistaken, where N is the number. The standard
> method involves dividing by successive primes (or successive integers
> in lieu thereof) until one finds either that J divides N or J*J > N.
> Multiplication and division are O((log N)^2) in this case (log N = # of digits;
> the algorithms are heavily dependent on the number of digits).
> There are sqrt(N) tests, each of which take 2 operations.

My text says "no one has yet devised an algorithm for deciding in polynomial time
whether a number is prime.

Is there a polynomial p and an algorithm A such that, for any positive integer n, A can
discover whether n is prime in just p(/log n\) steps? Here, we use /log n\ as a measure
of input length since it is assumed that n is being represented in binary notation.

...Numbers in range 2^400 take too long.

Imagine, then, an algorithm which, in the space of a few minutes, decides that

2^400 - 593 is prime with probability

0.999999999999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999999999999

<note> may not have exact number of 9's as the text, I will assume approximate
nature of the term 'few minutes' and the fact computers are 1000 times faster since
the text was written also demonstrates the above as a rough approximation of the
probability </note>

In fact, such an algorithm does exist. It was discovered by Michael O. Rabin
(another numerology name, Rapid!) and depends on the notion of integers
being "witness" to the compositeness of a number n. If a single witness can
be found n is composite, if a reasonable amount of time is spent searching
for witnesses and none can be found then n is exalted to primality with little
fear of being dethroned."

The only other requirement to get the high probability is

Theorem : if n is a composite number, more than half the numbers in the set
{2, 3, .... n-1} are witnesses to the compositeness of n.

Test whether n is prime :

1 Input n
2 Select m integers w1 .. wm at random from {2, 3, ...n-1}
3 Test if each wi is a witness
4 If none are witnesses output YES, else output NO

> >
> > Say the halting program is constructed the following way.
> >
> > the godel numbering or representation of programs as numeric from on the input tape
> > is structured in such a way that prime programs are witnesses to Halt.
> >
> > UTM(2)
> > UTM(3)
> > UTM(5)
> > UTM(7)
> > ...
> >
> > each take a program and its parameter as input
> >
> > UTM(7) m(i) = 1 IFF m(i) halts
> > UTM(7) m(i) = 0 <-> null witness
> >
> > Then all we need to do is try different primes until a 1 is detected and it proves it halts,
>
> That is a very strange machine encoding.
>

...
UTM(7) m(i) = 1 -> m(i) halts
UTM(11) m(i) = 1 -> m(i) halts
...

the IFF was too strong, no single program can determine if m(i) DOESNT halt.

Or the demonstration could be reversed, (the infinite set of halting programs where
we are guaranteed one of which) will detect any m(i) halts, or one of which
could detect it doesn't halt and to prove it halts you need many null witnesses.

Using the prime sequence of programs is just some example of an infinite subset
of partial Halt functions and is unrelated to the analogous example in prime number theory,
where the algorithm exists for poly time even if its not a bona fide algorithm, since it can
theoretically make an error.

Does this practical version of a halting function stand up to the halting proof, I'm
quite sure that it does.

Herc

Relevant Pages

  • Re: On The Proper Formulation Of The Halting Problem
    ... Is there a polynomial p and an algorithm A such that, for any positive integer n, A can ... If none are witnesses output YES, ... >> Say the halting program is constructed the following way. ... no single program can determine if mDOESNT halt. ...
    (sci.logic)
  • Re: On The Proper Formulation Of The Halting Problem
    ... Is there a polynomial p and an algorithm A such that, for any positive integer n, A can ... If none are witnesses output YES, ... >> Say the halting program is constructed the following way. ... no single program can determine if mDOESNT halt. ...
    (comp.theory)
  • Re: On The Proper Formulation Of The Halting Problem
    ... > polynomial time whether a number is prime. ... I've already given an algorithm guaranteed to work ... > 4 If none are witnesses output YES, ... > halt and to prove it halts you need many null witnesses. ...
    (comp.theory)
  • Re: On The Proper Formulation Of The Halting Problem
    ... > polynomial time whether a number is prime. ... I've already given an algorithm guaranteed to work ... > 4 If none are witnesses output YES, ... > halt and to prove it halts you need many null witnesses. ...
    (sci.math)
  • Re: On The Proper Formulation Of The Halting Problem
    ... > polynomial time whether a number is prime. ... I've already given an algorithm guaranteed to work ... > 4 If none are witnesses output YES, ... > halt and to prove it halts you need many null witnesses. ...
    (sci.logic)
Quantcast