CALTON@WASHINGTON.ARPA (11/01/83)
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!caltonjsol@bbncca.ARPA (Jon Solomon) (12/02/83)
I was looking at the infinite loop problem, and propose that if you look at
it as a timesharing problem thusly:
A user writes a program which is stuck in an infinite loop. He
doesn't know how to get out of it, or even that it exists. He just runs his
program (I'm thinking of the old days when we ran programs on cards). Sooner
or later someone else (an operator or systems programmer in this case) sees
the job chewing up resources and not doing anything useful. He kills the job
and sends a note (if he can) or otherwise gets in touch with the user
telling him that something needs to be looked at. The key here is that one
need not build a foolproof mechanism for "self awareness" or "self
observation" as long as there is some other entity who can look at the
state and interrupt its context if he thinks you need service.
Some people are in infinite loops for their entire lives (opinion).
Their "service interrupts" are ignored.
--
[--JSol--]
JSol@Usc-Eclc/JSol@Bbncca (Arpa)
JSol@Usc-Eclb/JSol@Bnl (Milnet)
{decvax, wjh12, linus}!bbncca!jsol