Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!security!genrad!decvax!harpo!seismo!hao!hplabs!sri-unix!CALTON@WASHINGTON.ARPA
From: CALTON@WASHINGTON.ARPA
Newsgroups: net.ai
Subject: Halting Problem: Resource Use
Message-ID: <13223@sri-arpa.UUCP>
Date: Mon, 31-Oct-83 18:45:12 EST
Article-I.D.: sri-arpa.13223
Posted: Mon Oct 31 18:45:12 1983
Date-Received: Sun, 6-Nov-83 10:23:49 EST
Lines: 48

From:  Calton Pu <CALTON@WASHINGTON.ARPA>

   From Shebs@Utah-20:

        The question is this: consider a learning program, or any
        program that is self-modifying in some way.  What must I do
        to prevent it from getting caught in an infinite loop, or a
        stack overflow, or other unpleasantnesses?  ...
        How can *it* know when it's stuck in a losing situation?

Trying to come up with a loop detector program seemed to find few enthusiasts.
The limited loop detector suggests another approach to the "halting problem".
The question above does not require the solution of the halting problem,
although that could help.   The question posed is one of resource allocation
and use.   Self-awareness is only necessary for the program to watch itself
and know whether it is making progress considering its resource consumption.
Consequently it is not surprising that:

        The best answers I saw were along the lines of an operating
        system design, where a stuck process can be killed, or
        pushed to the bottom of an agenda, or whatever.

However, Stan wants more:

        Workable, but unsatisfactory.  In the case of an infinite
        loop (that nastiest of possible errors), the program can
        only guess that it has created a situation where infinite
        loops can happen.

The real issue here is not whether the program is in loop, but whether the
program will be able to find a solution in feasible time.   Suppose a program
will take a thousand years to find a solution, will you let it run that long?
In other words, the problem is one of measuring gained progress versus
spent resources.   It may turn out that a program is not in loop but you
choose to write another program instead of letting the first run to completion.
Looping is just one of the losing situations.

Summarizing, the learning program should be allowed to see a losing situation
because it is unfeasible, whether the solution is possible or not.
>From this view, there are two aspects to the decision: the measurement of
progress made by the program, and monitoring resource consumption.
It is the second aspect that involves some "operating systems design".
I would be interested to know whether your parser knows it is making progress.


                -Calton-

        Usenet: ...decvax!microsoft!uw-beaver!calton