Re: On The Proper Formulation Of The Halting Problem

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 07/27/04 

Date: Tue, 27 Jul 2004 08:10:07 GMT

In sci.logic, |-|erc
<gotch@beauty.com>
 wrote
on Tue, 27 Jul 2004 01:40:36 GMT
<ooiNc.18287$K53.17154@news-server.bigpond.net.au>:
> "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.

Polynomial time in terms of what? Number of digits? Or the number?

If the number, I've already given an algorithm guaranteed to work
in sqrt(N) * (log N)^2 time, and log N space. (Basically,
just divide N by everything <= sqrt(N).)

If N=the number of digits, it gets a little harder; the division
check algorithm in that case would be N^2 * Exp(N/2) -- too long.

>
> 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.

A sieve would run from 1 to sqrt(n), so that's out. I'd have
to punt to more knowledgeable mathematicians at this point.

One amazingly fast algorithm is available that works for very
large numbers, but I don't know if it's polynomial or not.
It was implemented by Christian Bau, although I don't remember
who first discovered/developed it.

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

Define "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.

I'm not sure what a "witness" is in this context. It's true
that if N is prime, then no number J between 1 and N-1 has
gcd(J,N) != 1. Contrariwise, if N is not prime, then at least
2 numbers J and K are such that gcd(N,J) != 1 and gcd(N,K) != 1,
if N is not square -- and there are far more than 2, as any
multiple of J or K < N works as well. (If N is the square of
a prime P, at least P-1 numbers are not relatively prime thereto.)

>
> 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.

I don't know, offhand.

>
> Herc
>
>
> 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

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. ...
    (comp.theory)
  • 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.math)
  • 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
    ... >> polynomial time whether a number is prime. ... I've already given an algorithm guaranteed to work ... >> halt and to prove it halts you need many null witnesses. ... iff the program halts, or over half of the halt functions will output 1 iff it halts, whether ...
    (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 ... >> halt and to prove it halts you need many null witnesses. ... iff the program halts, or over half of the halt functions will output 1 iff it halts, whether ...
    (sci.math)