Will this *thread* ever halt? 
Author Message
 Will this *thread* ever halt?

Quote:


>>Yes, but do you want to have to be aware of exactly how much memory is
>>available to your programs?

>Not always. But, for the compiler to  warn me that
>"while(1)i =i+1" will either crash or cycle state forever does not require
>me to know this information.

Indeed. There are always simple cases which can be analysed easily. The
compiler I use gives warnings about while loops with constant boolean
conditions.

In general, though, determining whether a program will halt on a real
computer by analysing it as a FSM requires knowledge about exactly how much
memory is available.

Quote:
>>Consider the following pseudo-code:

>>i = 0
>>repeat
>>   allocate 1 byte of memory
>>   i++
>>until allocation fails
>>if i is prime, while(1);
>>end

>>You can write such a program in ANSI C. In order to predict whether it will
>>enter a non-terminating loop you have to know exactly how much memory is
>>available to the program when it runs, to the byte.

>If your point is that one can write ANSI "C" programs that are machine
>specific, sure.

The above program is not machine specific. You can write it so that it will
compile and run on any machine which supports ANSI C. You just can't tell
whether it will terminate or not unless you know exactly how much memory that
machine has.

Quote:
>            And if your point is that one can write ANSI "C" programs
>that will depend on I/O or operating system behavior, I also agree.
[...]
>The compiler cannot predict such paths, but it can warn us when our
>programs contain i/o dependent paths that can lead to indefinite cycles.

How many non-trivial C programs don't use dynamic memory allocation?  Sure,
you can restrict yourself to fixed-size data structures, but that leads to
even WORSE problems when you try to handle I/O.

Quote:
>Again, you raise a valid issue, but I'm not clear how it applies to the
>point at hand. If I write a program that can run correctly given a "C"
>compiler that uses 32bits to represent integers, but which will loop
>given an 8 bit "C" compiler, the compilers can flag the error, without
>requiring the programmer to worry about exact representation.

Eh?  The programmer wants his program to work. If it works for 32 bit ints
but not for 16 bit ints, then he has to worry about exact representation.
Having the compiler say "your program doesn't work because this machine has
16 bit ints" does not mean that the programmer doesn't have to worry about
it.

Quote:
>                                                            We provide
>abstractions in our programmng languages, but these are conveniences which
>do not negate the facts that real machines do not have "integers" and
>"real numbers", but only have limited representations of these mathematical
>abstractions.

"Real numbers" are a complete con. I'd rather leave them out of it.
"Integers" _do_ exist in some programming languages; the limitation is the
amount of hardware you give the language to work in. I have commented on this
in another posting.

Quote:
>         Even if the compiler implements "i" with a variable format
>(e.g. bignums), the programmer will want to know if the program may
>exceed thelimits of machine representation.

When working with integers mathematically you have to know whether your
result will become too big to work with on paper.

Quote:
>                                                 A correctly written program
>will not depend on exactly how much memory is available, and if the compiler
>flags such a dependency, then it has found what is most likely an error.

In that case, there are no correctly-written programs which perform
non-trivial tasks.

Quote:
>>The restrictions you have to place on a language in order to enable
>>guaranteed termination are such that the language is not useful for general
>>programming.

>Demonstrate this? Any demonstraton would seem to require unusually
>precise information about the limits of ingenuity.

I was talking in the present tense. If you want to start speculating wildly
about future developments in program proving, then go ahead.

I was also taking as given the assumption that most people require an
imperative language for general programming. Given the relative popularity of
pure functional languages vs C, BASIC, fortran and so on, I think that that is
reasonable.

Quote:
>>Secondly, I want to know whether my programs will work on my friends'
>>machines.

>Try compiling on those machines, or compile with a "portability" flag.

What is this "portability" flag supposed to do?  Not bother reporting about
termination?

Quote:
>If I had a "C" compiler that would run on, say, an IBM PC with at least
>6 meg of memory and a large disk, which would tell me within a few days
>whether or not an arbitrary "C" program would fail given at most
>X bytes of memory (X < 3 meg), then
>I believe that at least a few people would be interested
>in using it.

Indeed. But you can't do it. Even knowing the exact value of X doesn't help;
you have to know other things such as the value of the system clock.
(Consider "if seconds = 32 then while (1)").

You might be able to write a compiler which could predict whether or not a C
program would run on a machine with 3104272 bytes of memory, if started at
precisely 3:15:22 PM on Tuesday 21st May with no other programs resident.
Whether it would be worth your while to do so is another matter.

mathew



Fri, 05 Nov 1993 21:22:03 GMT  
 Will this *thread* ever halt?

Quote:
>yodaikenchelm.cs.umass.edu (victor yodaiken) writes:

>> I argue that it is possible, in theory, for a C compiler to detect all
>> paths that lead to non-terminating loops and to flag these paths.
>[ ... ]
>> If we give X.c to the hypothical smart compiler and it tells us that
>> X.c contains a path that exceeds the process memory limits on this
>> machine, or that X.c contains a path that will cause it to enter a
>> non-terminating loop if "alloc" fails, then the compiler has solved
>> the halting problem for this code.

>Good.  Perhaps Mr. Yodaiken would care to convince us infidels once and
>for all by posting some source code to do what he has so eloquently
>argued can be done?

I'm flattered that you have so much confidence in my abilites: if I can't
come up with an algorithm, then clearly, such an algorithm cannot exist.
There is an obvious, and obviously impractical algorithm, however. Let's
first consider the case of programs that just compute a function of
their arguments: i.e. programs that perform no i/o but  can be written
as subroutines of the form prog( type: x, type: y .... ).
For example, suppose we have a C function  "int f(x,y,z) int x,y,z ..."
Now we look at how "ints" are implemented on the target machine, suppose
that each int is a 32 bit value. We then emulate f(x,y,z) for each of
the mere 2^96 possible assignments. The emulation consists of single
stepping the computation of "f" either on the target computer or within
a program emulating this computer. At each step, we make a copy
of the entire memory space of the emulation. The program is sure to
either repeat state (a non-terminating loop) or exit within a bounded
amount of time because it can only reference a bounded amount of memory.

[BTW, this is not as impractical as it seems. H. Massalin has written
an ingenious assembly language optimizer that, given a short
assembly language routine that computes a simple result, will find the
shortest possible sequence of assembly statements that computes the
same function. Masslin's "Super-optimizer" essentially makes an
exhaustive search of the set of all 1 line assembly programs, then all
2 line programs, ..... With some smart heuristics the optimizer comes up with
some incredible sequences of code (e.g., a min function that has no
branch). There is a paper on the optimizer in some recent ASPLOS
proceeedings. So, enough of this whining about what we can't do. ]

Now we return to the impractical algorithm and extend it to programs that
have system calls. Ther are a couple of strategies here, but we'll take
the dumbest, since it requires the least effort  from me. Each system
call, i/o driven or not, changes program state in only a bounded number
of ways. For example, a call "read(filedescriptor,bufferaddr,n)"
will change the values of the "n" bytes of memory begining a
"bufferaddr" in some way. Whenever we encounter such a call in the
"C" program, we simply try all 2^(n*8) possibilities. Similarly, with
calls to "alloc" which either add some non-determined data to the program
data space (up to a known limit) or return a fail code. We just test
all branches. Pretty simple, hey?

This algorithm will work. And in some cases it might even be practical.
In hardware design it is already common to build special purpose machines
that do brute force emulations of chip behavior.  Is there a smarter
algorithm, a better programing language, a well defined o.s. interface
that will make this type of analysis practical without special purpose
hardware? No idea. But, there is emphatically no mathematical theorem
that eliminates the possibility of such an algorithm.

Quote:
>The proof of the pudding, Mr. Yodaiken, is in the eating.  You've argued
>that it's possible to decide the halting problem for "real computers".  
>So show us.



Sun, 07 Nov 1993 05:31:28 GMT  
 Will this *thread* ever halt?

Quote:


>]... I argue that it is possible, in theory, for a C
>]compiler to detect all paths that lead to non-terminating loops and to
>]flag these paths.

>I argue that this is impossible in theory.  Infinite-loop detection
>state space of the algorithm in question.  Furthermore, in the general
>case this information must almost certainly require space on the order
>of the size of the set of all possible states at a given point in the
>program (see H1 below).

>If so, the amount of information needed for at least some classes of
>programs is huge.  So there are programs that would compile without
>this analysis that cannot be compiled with this analysis.
>Furthermore, due to the magnitude of the information that the
>algorithm has to keep around, I'll bet that _most_ nontrivial programs
>could not be analysed in this way.

Your argument is that the task is difficult, and would require
huge resources, possibly impractical resources, for most non-trivial
programs. No disagreement here. Impractical != impossible. You must
understand "in theory" in a nonstandard way.

Quote:
>Of course you can always reduce the amount of information you keep
>around by compacting many states into a single approximating state.
>If you do this you can greatly increase the set of programs you can
>analyse, but your analysis is only approximate.  You can make the
>approximation a safe one or a complete one: A safe approximation will
>recognize all programs that definitely will _not_ halt.  A complete
>approximation will recognize all programs that definitely _will_ halt.
>I expect that these approximations can be made good enough to be very
>useful.

I suspect that you are right.

- Show quoted text -

Quote:
>Hypothesis H1:
>  any algorithm, HALT(p) that solves the halting problem for p must in
>general, for each point in p, encode at one time all the possible
>states that might occur at that point in p.

>Argument:
>  suppose HALT(p1) returns TRUE.  Create program p2 by adding
>somewhere the statement

>  if (F()) exit(); else for(;;);

>where F is a function whose output depends on most of the current
>state.  Then HALT must be able to determine whether F can ever
>possibly answer 0 in order to tell if p2 halts.  To do this, in
>general HALT must be able to encode all possible states that might
>occur at this point.  It is possible to construct sets of states that
>cannot be encoded by anything much smaller than the entire set of
>states.

That's an interesting conjecture. For many cases it would be easy, even
if "F" looks at all of memory. For example, if F computes a checksum on
all of memory, then the possible state set of F would be huge, but it
would be easy to see that F does return 0 sometimes. Essentially, we
want to know if there is a path through F that terminates at some
"return 0" state, but we don't want to have to build the whole damn
state set of F.  People in hardware boolean circuit optimization and
in formal verification have been looking at this problem. I'll dig
up some references if anyone wants. Clarke and Burch recently reported that
in verification of bit-slice controllers, the state set of 10^20 elements
did not have to be completely unrolled, and that only 60,000 ( ?) or
so states had to be visited. But, your mileage may vary.

Quote:
>Any HALT algorighm that attempts to avoid this by only doing one state
>at a time must in general deal with the possibility that HALT might
>not terminate, since it is simulating the program being analysed.  The
>same considerations apply to a program that works with subsets of the
>total set of possible states.

Yes. The HALT might not detect a loop, because it has thrown away the
loop start state.  Is that your point?


Sun, 07 Nov 1993 05:57:08 GMT  
 Will this *thread* ever halt?

Quote:
>In general, though, determining whether a program will halt on a real
>computer by analysing it as a FSM requires knowledge about exactly how much
>memory is available.

The way you cast the problem evades the TM/FSM question.  Yes. Programs
that depend on particularities of machine configuration do depend on
particularities of machine configuration. If we write a program P that
requests specific machine configuration information, and then choses
a path based on that data, then the operation of the program will not
be the same on all machines. But, this is essentially the same situation
as i/o dependencies. I argue that it is possible, in theory, for a C
compiler to detect all paths that lead to non-terminating loops and to
flag these paths. It is not possible for a "C" compiler to determine,
in advance, the result of checking the current time, asking how much
memory is available, or reading the next character typed on a terminal.
These questions are not undecidable in the technical sense, they are
simply undetermined.

Quote:
>How many non-trivial C programs don't use dynamic memory allocation?  Sure,
>you can restrict yourself to fixed-size data structures, but that leads to
>even WORSE problems when you try to handle I/O.

If we give X.c to the hypothical smart compiler and it tells us that
X.c contains a path that exceeds the process memory limits on this
machine, or that X.c contains a path that will cause it to enter a
non-terminating loop if "alloc" fails, then the compiler has solved
the halting problem for this code.

Quote:
>>Again, you raise a valid issue, but I'm not clear how it applies to the
>>point at hand. If I write a program that can run correctly given a "C"
>>compiler that uses 32bits to represent integers, but which will loop
>>given an 8 bit "C" compiler, the compilers can flag the error, without
>>requiring the programmer to worry about exact representation.

>Eh?  The programmer wants his program to work. If it works for 32 bit ints
>but not for 16 bit ints, then he has to worry about exact representation.
>Having the compiler say "your program doesn't work because this machine has
>16 bit ints" does not mean that the programmer doesn't have to worry about
>it.

You've lost me here. The correctness of "C" programs can depend on how
the compiler implements "ints". This is a feature of the "C" language, not
an artificial constraint that I'm inventing. Programmers cannot treat
"C" as if it were more high level than it is, and expect to get away with
it.

Quote:
>>                                                 A correctly written program
>>will not depend on exactly how much memory is available, and if the compiler
>>flags such a dependency, then it has found what is most likely an error.

>In that case, there are no correctly-written programs which perform
>non-trivial tasks.

Can you give me an example of such a program. The "C" compiler, lisp
interpreter, emacs editor, news-reader, operating system, computer
algebra programs and and theorem provers we have around here seem to
be able to tolerate wide variations in available memory.

Quote:

>>If I had a "C" compiler that would run on, say, an IBM PC with at least
>>6 meg of memory and a large disk, which would tell me within a few days
>>whether or not an arbitrary "C" program would fail given at most
>>X bytes of memory (X < 3 meg), then
>>I believe that at least a few people would be interested
>>in using it.

>Indeed. But you can't do it. Even knowing the exact value of X doesn't help;
>you have to know other things such as the value of the system clock.
>(Consider "if seconds = 32 then while (1)").

Again, you mistake the nature of the problem. If I claim that P
implements the function f: D -> D', then I am claiming that for any
x in the appropriate domain running P on input x will result in
the value f(x). If the compiler can tell me that there is an x inthe
domain that causes P to enter a non-terminating loop, then the compiler
has detected a bug in my program. You are arguing that the compiler will
not be able to predict x. So what? Generally, we want to know whether the
program will compute the correct value given any input, and we include
such things as system time among the inputs.


Sat, 06 Nov 1993 23:16:45 GMT  
 Will this *thread* ever halt?

Quote:
yodaikenchelm.cs.umass.edu (victor yodaiken) writes:
> I argue that it is possible, in theory, for a C compiler to detect all
> paths that lead to non-terminating loops and to flag these paths.
[ ... ]
> If we give X.c to the hypothical smart compiler and it tells us that
> X.c contains a path that exceeds the process memory limits on this
> machine, or that X.c contains a path that will cause it to enter a
> non-terminating loop if "alloc" fails, then the compiler has solved
> the halting problem for this code.

Good.  Perhaps Mr. Yodaiken would care to convince us infidels once and
for all by posting some source code to do what he has so eloquently
argued can be done?  And if Mr. Yodaiken is unable/unwilling to do so,
then is this "discussion" accomplishing anything more than blowing warm
air back and forth across the networks?

The proof of the pudding, Mr. Yodaiken, is in the eating.  You've argued
that it's possible to decide the halting problem for "real computers".  
So show us.

--
Saumya Debray           CS Department, University of Arizona, Tucson


     uucp:       uunet!arizona!debray



Sun, 07 Nov 1993 03:07:00 GMT  
 Will this *thread* ever halt?

]... I argue that it is possible, in theory, for a C
]compiler to detect all paths that lead to non-terminating loops and to
]flag these paths.

I argue that this is impossible in theory.  Infinite-loop detection
algorithms must almost certainly store some information about the
state space of the algorithm in question.  Furthermore, in the general
case this information must almost certainly require space on the order
of the size of the set of all possible states at a given point in the
program (see H1 below).

If so, the amount of information needed for at least some classes of
programs is huge.  So there are programs that would compile without
this analysis that cannot be compiled with this analysis.
Furthermore, due to the magnitude of the information that the
algorithm has to keep around, I'll bet that _most_ nontrivial programs
could not be analysed in this way.

Of course you can always reduce the amount of information you keep
around by compacting many states into a single approximating state.
If you do this you can greatly increase the set of programs you can
analyse, but your analysis is only approximate.  You can make the
approximation a safe one or a complete one: A safe approximation will
recognize all programs that definitely will _not_ halt.  A complete
approximation will recognize all programs that definitely _will_ halt.
I expect that these approximations can be made good enough to be very
useful.

Hypothesis H1:
  any algorithm, HALT(p) that solves the halting problem for p must in
general, for each point in p, encode at one time all the possible
states that might occur at that point in p.

Argument:
  suppose HALT(p1) returns TRUE.  Create program p2 by adding
somewhere the statement

  if (F()) exit(); else for(;;);

where F is a function whose output depends on most of the current
state.  Then HALT must be able to determine whether F can ever
possibly answer 0 in order to tell if p2 halts.  To do this, in
general HALT must be able to encode all possible states that might
occur at this point.  It is possible to construct sets of states that
cannot be encoded by anything much smaller than the entire set of
states.

Any HALT algorighm that attempts to avoid this by only doing one state
at a time must in general deal with the possibility that HALT might
not terminate, since it is simulating the program being analysed.  The
same considerations apply to a program that works with subsets of the
total set of possible states.

You can use the trick of running p in two different virtual machines,
one going twice as fast as the other, and comparing states.  The
storage overhead of this is equal to twice the size of the states of
p.  In this case, there are still programs that will compile without
HALT that will not compile with HALT -- so _theoretically_ this
doesn't solve the problem.  And it isn't practical either, since if
there is an infinite loop, it may take gigayears to find it.
--
                                        David Gudeman

noao!arizona!gudeman



Sun, 07 Nov 1993 03:49:35 GMT  
 Will this *thread* ever halt?



]>]... I argue that it is possible, in theory, for a C
]>]compiler to detect all paths that lead to non-terminating loops and to
]>]flag these paths.
]>I argue that this is impossible in theory.
]Your argument is that the task is difficult...
].. Impractical != impossible. You must understand "in theory" in a
]nonstandard way.

No, it's just that you seem to be trying to be trying to have it both
ways: "Since a computer has a finite number of states, it is possible
in principle to solve the halting problem for it, since you can always
just traverse all possible states."  The first part of the sentence
implies that you are modeling a computer as an FSM.  The second part
of the sentence implies that you are modeling a computer as a
non-finite state machine, since you are assuming that you can traverse
all possible states.

Pick your model.  No matter which one you pick, you cannot solve the
halting problem for all programs on a given machine with a program on
that machine.
--
                                        David Gudeman

noao!arizona!gudeman



Sun, 07 Nov 1993 12:53:07 GMT  
 Will this *thread* ever halt?

Quote:

>No, it's just that you seem to be trying to be trying to have it both
>ways: "Since a computer has a finite number of states, it is possible
>in principle to solve the halting problem for it, since you can always
>just traverse all possible states."  The first part of the sentence
>implies that you are modeling a computer as an FSM.  The second part
>of the sentence implies that you are modeling a computer as a
>non-finite state machine, since you are assuming that you can traverse
>all possible states.

You are defining the problem incorrectly. I do not argue that for any
FSM M, we can use M to decide its own halting problem. Instead, I argue
that there is a deterministic  *algorithm* with time/space bounded by the
number of states of M, and that this algorithm can decide the halting
problem for M. If we want, we can compute this algorithm on a FSM with
sufficient state space (probably quite a bit larger than M).

You are arguing that there are programs which can be executed on
any computer which use enough of the state space of the computer as to
leave no room for a program that would emulate them. But, of course.
However these programs *can* be emulated on a bigger, but still finite,
physical or virtual machine.  Note that there is no analog for this
procedure with TMs. A TM does not get any more powerful
when we add additional tapes or heads, but FSMs limited to n states
are strictly less powerful than FSMs limited to n+1 states.  



Sun, 07 Nov 1993 20:08:38 GMT  
 Will this *thread* ever halt?
Newsgroups: comp.lang.misc

Subject: Re: Will this *thread* ever halt?


Organization: Rockwell Collins, Cedar Rapids, IA

A general solution to the halting problem does not exist,
just as it is impossible to predict when this thread will halt!!

--

Michael Cook

"A little infrastructure goes a long way."  --  Stuart Shipman



Mon, 08 Nov 1993 04:24:00 GMT  
 Will this *thread* ever halt?
victor yodaiken:
   I argue that there is a deterministic *algorithm* with time/space
   bounded by the number of states of M, and that this algorithm can
   decide the halting problem for M. If we want, we can compute this
   algorithm on a FSM with sufficient state space (probably quite a
   bit larger than M).

Well, yes.  If you're dealing with an arbitrary machine, with 16k ram
(8 bit bytes) you have to have a state space of over 10^(10^6) bits to
store halting information (halts/doesn't) for every possible state.
And this doubles every time you add a bit to the machine -- for a unix
system with a gigabyte of disk space, your state space over
10^(8.26x10^10) bits (a number greater than 1 followed by over 82
billion zeros (decimal)).

An the other hand, many algorithms can be easily shown to halt.  (Any
algorithm which is "primitive recursive" in the number-theoretic
sense, which includes just about every computer programming technique
except arbitrary loops and arbitrary recursion).

So I can see why a person might want to say that the halting problem
is solvable for a practical machine, but I wouldn't say that using
state space is a useful solution.  The solution I see is to limit
yourself to a class of problems which are primitive recursive.

From personal experience, I can say that you're still going to have to
resort to state machine style techniques when you deal with i/o or
secondary storage (secondary storage being defined as any storage not
managed transparently by your target language).

And I'm sure that any systems implementor can tell you horror stories
about lurking race conditions and other potential bogosities in the os...

Raul Rockwell



Mon, 08 Nov 1993 08:41:26 GMT  
 Will this *thread* ever halt?

Quote:

> You are defining the problem incorrectly. I do not argue that for any
> FSM M, we can use M to decide its own halting problem. Instead, I argue
> that there is a deterministic  *algorithm* with time/space bounded by the
> number of states of M, and that this algorithm can decide the halting
> problem for M. If we want, we can compute this algorithm on a FSM with
> sufficient state space (probably quite a bit larger than M).

The original problem, as I recall, was whether a compiler can solve
the halting problem for real programs. I insist on being able to
run your compiler on the same machine I run my program on. (After
all, this is a real-world question and not some "silly" theoretical
exercise, right? :-)

  Ken Walker / Computer Science Dept / Univ of Arizona / Tucson, AZ 85721



Tue, 09 Nov 1993 00:10:46 GMT  
 Will this *thread* ever halt?

Quote:


> >In general, though, determining whether a program will halt on a real
> >computer by analysing it as a FSM requires knowledge about exactly how much
> >memory is available.
>                                           If we write a program P that
> requests specific machine configuration information, and then choses
> a path based on that data, then the operation of the program will not
> be the same on all machines.

OK. Give me an example of a C program which performs a major useful function,
and does not use any features which would make halting analysis of that
program dependent upon knowing exact details of the machine hardware.

Just one.

Quote:
>                      I argue that it is possible, in theory, for a C
> compiler to detect all paths that lead to non-terminating loops and to
> flag these paths.

No. It is possible in theory for a C compiler to detect all paths that MIGHT
lead to non-terminating loops. Anything more requires exact detailed
knowledge about the hardware.

And if you opt to flag all paths which MIGHT lead to non-terminating loops or
system crashes, you'll end up with most of the program being flagged.

Quote:
>                   It is not possible for a "C" compiler to determine,
> in advance, the result of checking the current time, asking how much
> memory is available, or reading the next character typed on a terminal.
> These questions are not undecidable in the technical sense, they are
> simply undetermined.

Right. But the former two are properties of the machine environment the
program will be running in, and can seriously affect whether the program
halts. Look at all the programs which crashed when the system date on UNIX
went past the size of an int.

You can, in certain languages, make halting predictions; you can say "If this
program is fed a file of finite size, it will terminate". C is not, in
general, one of those languages.

Quote:
> If we give X.c to the hypothical smart compiler and it tells us that
> X.c contains a path that exceeds the process memory limits on this
> machine, or that X.c contains a path that will cause it to enter a
> non-terminating loop if "alloc" fails, then the compiler has solved
> the halting problem for this code.

...on this particular machine, running at this particular time, with this
particular amount of processor stack, and so on.

To get any useful GENERAL halting results would require massive restrictions
on what you allowed in your "Halting ANSI C". Such severe restrictions that I
doubt whether the language would be useful.

Quote:
> >Eh?  The programmer wants his program to work. If it works for 32 bit ints
> >but not for 16 bit ints, then he has to worry about exact representation.
> >Having the compiler say "your program doesn't work because this machine has
> >16 bit ints" does not mean that the programmer doesn't have to worry about
> >it.

> You've lost me here. The correctness of "C" programs can depend on how
> the compiler implements "ints". This is a feature of the "C" language, not
> an artificial constraint that I'm inventing. Programmers cannot treat
> "C" as if it were more high level than it is, and expect to get away with
> it.

Right. And whether a C program halts or not can be critically dependent upon
the size of integers used in that particular implementation of C.

So to perform your magic halting analysis, you need to know exactly how big
integers are. And if your analysis is to be useful, this information needs to
be directly or indirectly communicated to the programmer. Therefore the
programmer needs to worry about exact implementation specifics.

Quote:
> >>                                                 A correctly written progra
> >>will not depend on exactly how much memory is available,

> >In that case, there are no correctly-written programs which perform
> >non-trivial tasks.

> Can you give me an example of such a program. The "C" compiler, lisp
> interpreter, emacs editor, news-reader, operating system, computer
> algebra programs and and theorem provers we have around here seem to
> be able to tolerate wide variations in available memory.

Really?  Try running them in 1KB.

There will be some lower memory threshold x beneath which the programs will
not run. If you have x-1 bytes of memory, the programs will not run. It is
therefore important that the exact amount of memory you have is greater than
x. This is a condition on exactly how much memory must be available. Equality
isn't the only condition which requires you to know exact amounts.

Quote:
> >>If I had a "C" compiler that would run on, say, an IBM PC with at least 6
> >>meg of memory and a large disk, which would tell me within a few days
> >>whether or not an arbitrary "C" program would fail given at most X bytes
> >>of memory
[...]
> >Indeed. But you can't do it. Even knowing the exact value of X doesn't help;
> >you have to know other things such as the value of the system clock.
[...]
> Again, you mistake the nature of the problem. If I claim that P
> implements the function f: D -> D', then I am claiming that for any
> x in the appropriate domain running P on input x will result in
> the value f(x). If the compiler can tell me that there is an x inthe
> domain that causes P to enter a non-terminating loop, then the compiler
> has detected a bug in my program. You are arguing that the compiler will
> not be able to predict x. So what? Generally, we want to know whether the
> program will compute the correct value given any input, and we include
> such things as system time among the inputs.

You said "an arbitrary C program". Not "an arbitrary C program which is not
allowed to look at the system time".

If your C code is not allowed to look at the system time, not allowed to use
malloc (which effectively involves looking at available memory), not allowed
to look at the file system (for temporary files) and so on, then yes, you
probably can find out whether it will compute the correct value given any
input.

Now, how many useful programs do you know which satisfy those criteria?

To look at it another way: Most C programs will end up with a list of inputs
which includes system memory, clock, stack size, file system size, and so on.
You will need to know the values of these inputs before you can determine
whether the program will halt or not. This is not very useful.

I'm about ready to give up arguing with you. You seem to be just as clueless
as when you started, and I really have better things to do than argue about
whether you can solve the halting problem for general ANSI C programs.

If you still believe you can determine whether an arbitrary non-trivial ANSI
C program will halt or not, and have that information generally applicable
enough to be useful to the programmer, then go out there and do it and earn
yourself millions. While you're at it, there are some guys in sci.skeptic who
have a design for a perpetual motion machine which needs development.

mathew



Sun, 07 Nov 1993 18:59:58 GMT  
 Will this *thread* ever halt?

Quote:


>> >In general, though, determining whether a program will halt on a real
>> >computer by analysing it as a FSM requires knowledge about exactly how much
>> >memory is available.

I'm really mystified by this discussion. Part ofthe problem may arise from
the odd idea of "exact" that you seem to hold.
You write:

Quote:
>There will be some lower memory threshold x beneath which the programs will
>not run. If you have x-1 bytes of memory, the programs will not run. It is
>therefore important that the exact amount of memory you have is greater than
>x. This is a condition on exactly how much memory must be available. Equality
>isn't the only condition which requires you to know exact amounts.

Forgive me if I mistake your meaning, but this seems like complete nonsense.
The expression x> 10 does not constrain x  to an "exact amount".
If emacs requires at least 4 meg of memory in order to run correctly,
then knowing that x>4meg is certainly good enough.

A second problem arises from your misuse of the term "halting problem".
The halting problem involves deterministic machines. It does not
involve predicting the time of day which you will chose to run
a program or the next word which I will type into a keyboard.
A computer program can be considered to be a deterministic machine
computing a function on its input. You want to say that program behavior
is not deterministic, because the input is not deterministic.  Generally,
however, we are less interested in predicting system input than in making
sure that the program can cope correctly with *every* possible input.
When I say that we can, in theory,  decide whether or not a "C"
program contains an non-terminating loop, I do not mean to suggest
that we can decide in advance whether or not it will ever enter that
loop. The program "read c; if c='\n' while(1); exit" contains
a reachable non-terminating loop. You may be content
to run this program without ever hitting a cariage return. I'm not,
however, interested in predicting your behavior.

Quote:

>> Again, you mistake the nature of the problem. If I claim that P
>> implements the function f: D -> D', then I am claiming that for any
>> x in the appropriate domain running P on input x will result in
>> the value f(x). If the compiler can tell me that there is an x inthe
>> domain that causes P to enter a non-terminating loop, then the compiler
>> has detected a bug in my program. You are arguing that the compiler will
>> not be able to predict x. So what? Generally, we want to know whether the
>> program will compute the correct value given any input, and we include
>> such things as system time among the inputs.

You reply:
>You said "an arbitrary C program". Not "an arbitrary C program which is not
>allowed to look at the system time".

Here, I'm considering the program as a function with input varying over
its domain. In this case, consider the domain to be the set of possible
time values. We don't want to attempt to predict which elements of this
domain will be encountered: i.e., we don't want to try to predict the
time of day when the program will be run. We just want to make sure that
the program behaves "correctly" for any time value.

Quote:
>I'm about ready to give up arguing with you. You seem to be just as clueless
>as when you started, and I really have better things to do than argue about
>whether you can solve the halting problem for general ANSI C programs.

Go to 'em.


Tue, 09 Nov 1993 22:41:37 GMT  
 Will this *thread* ever halt?

Quote:

> Forgive me if I mistake your meaning, but this seems like complete nonsense.
> The expression x> 10 does not constrain x  to an "exact amount".

No. It does, however, constrain x to be greater than some exact amount. As
opposed to being greater than some fuzzily-defined amount which is
approximately 10.

Quote:
> If emacs requires at least 4 meg of memory in order to run correctly,
> then knowing that x>4meg is certainly good enough.

It depends. It might require significantly more memory than that if you're
editing large files. The amount of memory required by Emacs is not an exact
amount. It depends what you're doing with the program.

Part of the job of determining whether an ANSI C program will halt will
involve placing exact bounds on how much memory it might use in running, and
hence producing exact specifications of input values/conditions for which it
might not terminate. And remember that a single byte might make a difference;
so if it's December, your calendar program might fail to work properly
whereas it worked fine in May, because somewhere the program is allocating
space for the name of the month and this is resulting in its not having
enough space to complete some other task.

Quote:
> The halting problem involves deterministic machines. It does not
> involve predicting the time of day which you will chose to run
> a program or the next word which I will type into a keyboard.

I didn't mean to imply that it did.

Quote:
> A computer program can be considered to be a deterministic machine
> computing a function on its input. You want to say that program behavior
> is not deterministic, because the input is not deterministic.  Generally,
> however, we are less interested in predicting system input than in making
> sure that the program can cope correctly with *every* possible input.

Right. So in addition, your Terminating ANSI C has to check whether all
possible return values from standard library calls will result in termination
or not. For example, if the program uses time.h, we must check to see that it
terminates for all possible start times.

Basically, it adds another dimension of complexity to the problem.

Quote:
> >You said "an arbitrary C program". Not "an arbitrary C program which is not
> >allowed to look at the system time".

> Here, I'm considering the program as a function with input varying over
> its domain. In this case, consider the domain to be the set of possible
> time values. We don't want to attempt to predict which elements of this
> domain will be encountered: i.e., we don't want to try to predict the
> time of day when the program will be run. We just want to make sure that
> the program behaves "correctly" for any time value.

Right. That's fine.

Basically, for any moderately complicated ANSI C program the dimensions of
the input domain and the range of each dimension will be so large that trying
all combinations will be infeasible on even the largest computers. I'll leave
it to someone else to do some sums to demonstrate this.

In short, determining the halting status of ANSI C programs is not feasible
for real programs; and it's not possible for general ANSI C programs, because
general ANSI C programs might have arbitrarily large input spaces making
analysis require impossible amounts of memory and CPU time.

If you want to write programs and be told whether they will halt or not, you
will have to use a different language; one which is restricted so that you
don't have to rely on brute-force methods for determining halting status. For
example, a functional language which uses map operations (iteration over a
structure) rather than while loops and which limits general recursion.

mathew



Sun, 14 Nov 1993 00:09:31 GMT  
 Will this *thread* ever halt?

Quote:
>In short, determining the halting status of ANSI C programs is not feasible
>for real programs; and it's not possible for general ANSI C programs, because
>general ANSI C programs might have arbitrarily large input spaces making
>analysis require impossible amounts of memory and CPU time.

I don't see why all that stuff is even being discussed; like I pointed out
the other day, even determining halting for self-contained C programs (no
malloc, no clock dependency, etc) is impossible, so why bring in the other
junk?

Quote:
>If you want to write programs and be told whether they will halt or not, you
>will have to use a different language; one which is restricted so that you
>don't have to rely on brute-force methods for determining halting status. For
>example, a functional language which uses map operations (iteration over a
>structure) rather than while loops and which limits general recursion.

If you are aware of work that shows that the halting problem is soluble
for functional languages, I would dearly love to see the reference. Or
even that it *might* be soluble. (In other words, I don't believe it for
a minute; functional languages are universal computational models and
as such can be mapped one-to-one with Turing machines and the lambda calculus
etc.)

Also, you and your conversational opponent are starting to sound like you're
in {*filter*} agreement. No doubt that's just because I've lost track of your
actual base positions.
        Doug
--


Professional Wild-eyed Visionary        Member, Crusaders for a Better Tomorrow



Sun, 14 Nov 1993 04:44:34 GMT  
 
 [ 57 post ]  Go to page: [1] [2] [3] [4]

 Relevant Pages 

1. Will this *thread* ever halt?

2. Halting Ruby's threading

3. Halt doesn't halt.

4. Have you ever seen a thread ?

5. Longest Thread Ever

6. Threads creating threads creating threads...

7. thread, threading, mutex modules and non-threading interpreters

8. Clarion Project - Anyone willing to help?

9. Willing to pay for help with error (CW2.003)

10. Someone willing to donate TXD parsing code to Open Clarion

11. URGENT: someone willing to decompile Summer '85 file

12. Anyone willing to help a beginner?

 

 
Powered by phpBB® Forum Software