Re: the Halting Problem has a lot to it

From: Martin Shobe (mshobe_at_sbcglobal.net)
Date: 07/11/04 

Date: Sun, 11 Jul 2004 13:22:21 GMT

On 11 Jul 2004 00:41:14 -0700, starofbabylon@yahoo.com
(Babylonian_Astrologer) wrote:

>Martin Shobe <mshobe@sbcglobal.net> wrote in message news:<04v0f0tu6j56b2f0c5usnegrv70jot48le@4ax.com>...
>> On 10 Jul 2004 15:20:13 -0700, starofbabylon@yahoo.com
>> (Babylonian_Astrologer) wrote:
>>
>> >Martin Shobe <mshobe@sbcglobal.net> wrote in message news:<ik80f0djj1k55g99k78je9h7aj4q3j23k5@4ax.com>...
>> >> Not really. The following becomes a solution (if I'm reading you
>> >> correctly).
>> >>
>> >> H(I,j)
>> >> {
>> >> while (1);
>> >> }
>> >>
>> >> Martin
>> >
>> >
>> >So what if it is?
>>
>> Solving it is trivial.
>>
>>
>> Yep. In fact, one can always add more Turing machines that it does
>> solve for (instead of looping).
>>
>> Martin
>>
>>
>> >Are there no others?
>
>But, maybe there are general soloutions whose only vulnerability are
>these parameter-doubling loops. I guess that's what I was thinking. I
>had in mind something that worked like a modified UTM. I guess I'm
>being vague...

I doubt it. The reason we use those loops is because they are a very
simple counter-examples. It's very easy to show that Halts will fail
for them. That said, you might be able to solve it for enough
programs that it becomes practicle. You'll just have to live with the
fact that every now and then, it will fail.

Martin

Relevant Pages

  • Re: Home early
    ... Martin Bowers has been pushing me around ... and doing all the lock wheeling too. ... Dreamcatcher is now back at Lower Heyford awaiting a BSS examination ... It will fail. ...
    (uk.rec.waterways)
  • Re: dynamic type checking - a pauline conversion?
    ... Robert C. Martin wrote: ... >>example in a common superclass like Object) or do we expect the method ... >>send to fail at runtime when the specific class doesn't implement ...
    (comp.object)
  • Re: BOKO death
    ... Martin wrote: ... decided to fail today :-( ... Questions - what's the easiest method to get the data off the HD? ... Put someone else's battery into it, and get off all the data while you ...
    (uk.comp.sys.mac)
  • Re: Very strange transistor problem.... Sys 11A
    ... Most manufacturers don't specify gain with the collector and emitter ... Thanks, Martin. ... without fail, until you sell it and then it flakes out the very next ...
    (rec.games.pinball)
  • 5.x test request (FWD: Repairing ext2fs stat(2), fts(3) in 6.0-current, please test on 5.x)
    ... Martin ... ext2fs fails to set the device in the statsystem call. ... Subsequently, that makes ftsfail, which goes as far as make ls ... I don't have an infinite number of cats. ...
    (freebsd-stable)