Path: utzoo!attcan!uunet!midway!ncar!elroy.jpl.nasa.gov!usc!zaphod.mps.ohio-state.edu!rpi!uupsi!sunic!cs.umu.se!christer
From: christer@cs.umu.se (Christer Ericson)
Newsgroups: comp.lang.misc
Subject: Halting theory in practice (was Re: Array references cannot be made optimal)
Message-ID: <1990Nov15.101516.12198@cs.umu.se>
Date: 15 Nov 90 10:15:16 GMT
References: <3975:Nov1323:25:4390@kramden.acf.nyu.edu> <1990Nov14.150535.25991@cs.umu.se> <13530:Nov1419:56:3790@kramden.acf.nyu.edu>
Sender: news@cs.umu.se (News Administrator)
Organization: Dep. of Info.Proc, Umea Univ., Sweden
Lines: 56

In article <13530:Nov1419:56:3790@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>In article <1990Nov14.150535.25991@cs.umu.se> christer@cs.umu.se (Christer Ericson) writes:
>> In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> [ stuff deleted ]
>
>> If a program, or rather a computer, is restricted to
>> a finite number of states (which all modern computers are) then it's nothing
>> more than a finite automaton and therefore the halting problem for these
>> machines is solvable *in theory*.
>
>Right. It's also solvable in practice.
>
>> Practically, given the size of available
>> memory on todays machines, for most problems I'd say it's not.
>
>Are you trying to contribute to this discussion? In the article you're
>responding to I gave quite precise estimates of the amount of work
>necessary: twice as much memory for the variables you want to detect
>cycling, and three times slower not counting housekeeping whenever those
>variables are used. Now you express some vague opinion that this is not
>practical, when obviously factors of two and three are the norm during
>debugging.

I'd like to see you try your method on a program like

	(defun foo (n) (if (= n 0) t (foo (1+ n))))

and calling the function with n=1. On a system with bigints and lots of
memory, this isn't practical. If the function was more complex so it wasn't
feasible to solve the halting problem by hand, and if it did get into a loop
(when it ran out of memory, and the bigints overflow or whatever) the running
time of the program could very well be more than, say, a year and three years
to solve the halting problem *isn't* what I'd call practical. Now, for your
average program, with a more normal running time it sure is practical, no
question about it!

>> Also, the metod
>> you described is nothing new, it's a commonly used metod to find cycles in
>> iterative procedures
>
>In fact, I didn't even bother to review the details of how to detect
>loops in general, because any reader who doesn't understand can look up
>the exercises in Knuth.
>
>> Solving the halting problem for a Turing machine
>
>We are talking about practical problems, not Turing machines.

You do have a tendency to remove sentences from their context, don't you?
Besides, what's all the fuzz about? I'm agreeing with you (more or less),
ain't I?

>---Dan

| Christer Ericson            Internet: christer@cs.umu.se [130.239.1.101] |
| Department of Computer Science, University of Umea, S-90187 UMEA, Sweden |