Halting Problem Solved! Film at 11! (Was Re:
Author Message
Halting Problem Solved! Film at 11! (Was Re:

]
]|If you want to get theoretical, then you can _theoretically_ keep
]
]There is definitely and without question a finite amount of matter in
]the universe that I am willing to make tapes out of.
]
]Evidently, I disagree. I am PERSONALLY willing to engineer my
]compilers on the assumption that (a) FTL travel, (b) many-worlds
]parallelism and (c) anything comparably revolutionary will not become
]available within the useful lifetime of the software.

Not fair, Stephen.  You took the theoretical argument and made
of whether a computer is _theoretically_ a finite state machine -- and
I covered the practical issues in the part you did not cite.
--
David Gudeman

noao!arizona!gudeman

Mon, 25 Oct 1993 01:56:03 GMT
Halting Problem Solved! Film at 11! (Was Re:

|]
|]|If you want to get theoretical, then you can _theoretically_ keep
|]
|]There is definitely and without question a finite amount of matter in
|]the universe that I am willing to make tapes out of.
|]
|]Evidently, I disagree. I am PERSONALLY willing to engineer my
|]compilers on the assumption that (a) FTL travel, (b) many-worlds
|]parallelism and (c) anything comparably revolutionary will not become
|]available within the useful lifetime of the software.
|
|Not fair, Stephen.  You took the theoretical argument and made
|of whether a computer is _theoretically_ a finite state machine -- and
|I covered the practical issues in the part you did not cite.

I wasn't cheating, I was just trying to reiterate - and defend - a
particular cut on the problem. There was a particular view given here
that it is interesting to study the THEORETICAL properties of
PRACTICAL machines.  I *could* talk about the theoretical properties
of theoretical machines or about the practical properties of practical
machines, yes, and that would be "fairer pool" in that it would
disagree!

The point is: bar some MAJOR breakthroughs in physics, the machines we
WORK with have limits. The fact that machines have limits has
potential theoretical implications. It is proposed by some to explore
them.

Objections that theoretical machines lack practical limits or that the
practical limits of practical machines are more immediate are SIMPLY
NOT GERMANE.

Let me try one more time. PRACTICAL computers are FSMs and not fully
general turing machines because PRACTICAL computers are finite. The
fact that PRACTICAL computers are finite is an important THEORETICAL
property of PRACTICAL computers and may need to be addressed before
certain ideas are dismissed. And this is true even if you include all
the input they're ever going to get as state space.

...I feel a bit like you're telling me that it's impossible to code a
correct sort, because you never know when your input is going to be
an infinite stream and the function just might not terminate....
----------------------------------------------------------------------
stephen p spackman         Center for Information and Language Studies
systems analyst                                  University of Chicago
----------------------------------------------------------------------

Mon, 25 Oct 1993 16:22:58 GMT
Halting Problem Solved! Film at 11! (Was Re:

]
]... PRACTICAL computers are FSMs and not fully
]general turing machines because PRACTICAL computers are finite. The
]fact that PRACTICAL computers are finite is an important THEORETICAL
]property of PRACTICAL computers and may need to be addressed before
]certain ideas are dismissed...

I'm assuming that by "practical computers are finite" you mean that
computers are finite for practical purposes -- if you meant something
else, please correct me.  OK, suppose that there are important
theoretical results based on the assumption that computers are finite.
That does not preclude the possibility that there are important
theoretical results based on the assumption that computers are not
finite.  And it is certainly the case that there are many applications
where computers are not finite -- for practical purposes.

I have not claimed that computers are unbounded-state machines, I've
only said that it isn't the case that computers are obviously FSMs as
some on this group seem to think.  Both models of computers have their
uses.  It is not the case that all results based on the assumption
that computers are USMs are impractical, because as long as your
problems do not hit the boundaries, the boundaries may as well not
exits.  Most algorithm analyses and programming language semantics
assume that the machines are USM's and the results from such
assumptions are valid for most practical purposes.

]....I feel a bit like you're telling me that it's impossible to code a
]correct sort, because you never know when your input is going to be
]an infinite stream and the function just might not terminate....

I don't understand what you mean by that.  If your input is another
process of unknown origin, then there _are_ certain correctness
criteria that you cannot satisfy with your own sort.  Are you
suggesting that you wouldn't want to be told that?
--
David Gudeman

noao!arizona!gudeman

Tue, 26 Oct 1993 03:15:58 GMT
Halting Problem Solved! Film at 11! (Was Re:

Quote:
>Let me try one more time. PRACTICAL computers are FSMs and not fully
>general turing machines because PRACTICAL computers are finite. The
>fact that PRACTICAL computers are finite is an important THEORETICAL
>property of PRACTICAL computers and may need to be addressed before
>certain ideas are dismissed. And this is true even if you include all
>the input they're ever going to get as state space.

PRACTICAL computers may be FSM's but programming languages are not.  Nowhere
in the ANSI C standard does it give a maximum amount of memory that a C
program can run in.  Thus your program checker must assume that the program
that it is analyzing will never run out of tape, which means that the analyzer
must assume that the program will run on a Turing Machine, and the
undecidability theorem applies.

Quote:

>...I feel a bit like you're telling me that it's impossible to code a
>correct sort, because you never know when your input is going to be
>an infinite stream and the function just might not terminate....

Of course some simple argorithms may be proven, like a sorting algorithm,
but not >ALL<
--
David Gottner

{...}ncar!ico!auto-trol!younam                 12500 North Washington Street
(303) 252-2321                                 Denver, CO 80241-2404

Tue, 26 Oct 1993 04:54:01 GMT
Halting Problem Solved! Film at 11! (Was Re:

|]
|]... PRACTICAL computers are FSMs and not fully
|]general turing machines because PRACTICAL computers are finite. The
|]fact that PRACTICAL computers are finite is an important THEORETICAL
|]property of PRACTICAL computers and may need to be addressed before
|]certain ideas are dismissed...
|
|I'm assuming that by "practical computers are finite" you mean that
|computers are finite for practical purposes -- if you meant something

No. I mean that practical computers are ACTUALLY finite: for both
practical AND theoretical purposes. I don't know any simpler way of
phrasing this. Practical computers are finite. They ARE. Really. In
actuality, real, actual, practical computers are actually really
finite in every way. They are limited, bounded and finite. Really.

|                           OK, suppose that there are important
|theoretical results based on the assumption that computers are finite.
|That does not preclude the possibility that there are important
|theoretical results based on the assumption that computers are not
|finite.

Of course not. But any important theoretical result that DEPENDS on a
computer being infinite will have NO DIRECT APPLICATION to computers,
since actual computers are not, EVER, infinite.

|         And it is certainly the case that there are many applications
|where computers are not finite -- for practical purposes.

This is absurd. Of course there are applications in which a finite
practical machine of certain capacity and an infinite theoretical
machine would exhibit the same behaviour. But does this make the
finite machine less finite? No way, no how. Practical computers are,
for all purposes, always finite. That's just the way it is. Any
infinite computer is a mere approximation of a real computer and you
use techniques and results derived for infinite computers at your own
peril.

|I have not claimed that computers are unbounded-state machines, I've
|only said that it isn't the case that computers are obviously FSMs as
|some on this group seem to think.

I don't understand what you're saying here. Are you telling me that
you actually KNOW that computers are FSMs but that you consider this
fact sufficiently non-obvious that you feel justified in persisting in
the pretence that they are infinite, despite the facts? Or are you
merely defending OTHER people's rights to err without fear of
correction?

In any event, the finitude of computers is obvious to about the same
extent as it is obvious that the population of ducks in Tahiti is
finite, I'd say. I mean, computers are finite, have discrete states,
and are machines. Therefore they're REALLY QUITE LIKELY (ahem) to be
FSMs.

|                                  Both models of computers have their
|uses.

You bet. No question.

|      It is not the case that all results based on the assumption
|that computers are USMs are impractical, because as long as your
|problems do not hit the boundaries, the boundaries may as well not
|exits.

EXACTLY!!!! THANKYOU!!!! THIS IS THE POINT!!!! And any theorem that
depends on the fact that the machine will *NOT* hit a boundary does
not in fact apply to a real computer - and this is true any theorem
that requires that encodings exist for arbitrary objects, for example.
Remember: computers FINITE and (like humans) CANNOT DO ARITHMETIC.

|        Most algorithm analyses and programming language semantics
|assume that the machines are USM's and the results from such
|assumptions are valid for most practical purposes.

Oh, yes. Correct me if I'm wrong, but it seems to me that they are not
adequate to THEORETICAL purposes like the standard
incompleteness/inconsistency proofs. You're confusing building up with
building down: these theorems, at least as I've seen them, apply to
"computers" that are AT LEAST infinite, not to ones that are AT MOST
infinite.  They may be useful approximations, but they aren't precise
results.

|]....I feel a bit like you're telling me that it's impossible to code a
|]correct sort, because you never know when your input is going to be
|]an infinite stream and the function just might not terminate....
|
|I don't understand what you mean by that.  If your input is another
|process of unknown origin, then there _are_ certain correctness
|criteria that you cannot satisfy with your own sort.  Are you
|suggesting that you wouldn't want to be told that?

No; I'm suggesting that it's important to attribute cause accurately.
There's nothing INCORRECT about my sort, just because it can be handed
unbounded input. And there's nothing INFINITE about my computer just
because it can be approximated in some respects by an infinite
machine.
----------------------------------------------------------------------
stephen p spackman         Center for Information and Language Studies
systems analyst                                  University of Chicago
----------------------------------------------------------------------

Tue, 26 Oct 1993 15:13:11 GMT
Halting Problem Solved! Film at 11! (Was Re:

|PRACTICAL computers may be FSM's but programming languages are not.  Nowhere
|in the ANSI C standard does it give a maximum amount of memory that a C
|program can run in.  Thus your program checker must assume that the program
|that it is analyzing will never run out of tape, which means that the analyzer
|must assume that the program will run on a Turing Machine, and the
|undecidability theorem applies.

I never disagreed. But.

First of all, I would be more interested in a verifier that told me
about what my programme would do *if compiled* than one that told me
what it would do if run on a non-realisable machine.

Secondly, your argument applies to languages as they are presently
defined; personally I wouldn't BOTHER writing a verifier for C (though
if I had one there are times when I'd use it). A *new* type system,
for instance, might be able to get very good mileage out of the
assumption that resources are finite (though I'd be very unhappy if it
assumed any PARTICULAR bound, I think). I wouldn't know, of course;
I'm no theorist.

But I grant your point: a C programme could consume an unbounded
amount of stack and still be correct by the standard (though it would
take a VERY imaginative implementation to get the heap to contain
more than ULONG_MAX distinct objects, whatever ULONG_MAX is).

But frankly, I think I'd rather have that flagged as an error, even if
that's technically wrong! (Not that this invalidates your point.)

Honestly I didn't think this was what we were talking about....
----------------------------------------------------------------------
stephen p spackman         Center for Information and Language Studies
systems analyst                                  University of Chicago
----------------------------------------------------------------------

Tue, 26 Oct 1993 16:04:59 GMT
Halting Problem Solved! Film at 11! (Was Re:
Stephen P Spackman:
Oh, yes. Correct me if I'm wrong, but it seems to me that they are
not adequate to THEORETICAL purposes like the standard
incompleteness/inconsistency proofs.

Which is not at all to say that a computer is complete -- if it was
you wouldn't have to worry about being able to write programs that can
not run because of machine limits :-)

Raul Rockwell

Tue, 26 Oct 1993 21:41:51 GMT
Halting Problem Solved! Film at 11! (Was Re:
A quick note that might serve to end all this fuss:

It seems to me that many of you are busy energetically expounding on
a different question than the one which whoever-started-this intended

given program P in language L, I want an analyser that will say:
P does not halt for these inputs: <list>
P might or might not halt for these inputs: <list>
and I would like as few of the latter answers as possible.

For instance, given the program [yes, I use `unnecessary' semicolons]

program p (input, output);
procedure spin; begin while true do {nothing}; end;
var v : integer;
begin
write('gimme a number');
if v < 0 then spin;
end.

we would like to have the program analyser say:

P does not halt when the input value is less than zero.

We would not like to have it say:

P might or might not halt for any input.

but the latter is acceptable when P is `sufficiently complicated'.
--
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427)

Tue, 26 Oct 1993 22:33:37 GMT
Halting Problem Solved! Film at 11! (Was Re:

Quote:

>First of all, I would be more interested in a verifier that told me
>about what my programme would do *if compiled* than one that told me
>what it would do if run on a non-realisable machine.

You are right, a good verifier should be able to tell you approximately how much
time/space overhead a program will require.  (After all, humans can do this for
algorithms, so a verifier should be able to do so also)

However suppose the verifier said "This program will not halt on a machine
with no more than 16 MB"  Well, we can get a 32MB machine and run it.  In
otherwords if the verifier can show the program works or doesn't work on
a machine with memory <= M, then we can run it on a machine with memory M+1.
Thus, there is really no way to avoid Turing undecideability.

Quote:
>Secondly, your argument applies to languages as they are presently
>defined; personally I wouldn't BOTHER writing a verifier for C (though
>if I had one there are times when I'd use it). A *new* type system,
>for instance, might be able to get very good mileage out of the
>assumption that resources are finite (though I'd be very unhappy if it
>assumed any PARTICULAR bound, I think). I wouldn't know, of course;
>I'm no theorist.

>But I grant your point: a C programme could consume an unbounded
>amount of stack and still be correct by the standard (though it would
>take a VERY imaginative implementation to get the heap to contain
>more than ULONG_MAX distinct objects, whatever ULONG_MAX is).

I don't think I'd want to use a language that placed limits on the number
of active objects (unless it is a large limit like ULONG_MAX :-) )
--
David Gottner

{...}ncar!ico!auto-trol!younam                 12500 North Washington Street
(303) 252-2321                                 Denver, CO 80241-2404

Fri, 29 Oct 1993 12:13:10 GMT
Halting Problem Solved! Film at 11! (Was Re:

[about the halting problem for real computers]
]Ack!  I apologize for wasting net bandwidth.  The following article answers
]this question:

I missed the original article, but no, it does not answer the
question, it only confuses it further.

]>[A finite TM is translatable into a FSM.  A FSM has a state space S and a
]>mapping S -> S.  To see if it halts, pick a starting state, run through the
]>sequences.  If if goes on the halt state then it halts.  If it ever touches a
]>state which already occured, it doesn't.  Since there is only a finite number
]>of states, it takes a finite amount of time to decide (since at most it has
]>to go through all the states)]

What machine is going to do this?  If computers are FSM's then you
only have an FSM to do this, and I can always find a program too big
to analysis in this way.

By the way, how do you know that the TM is finite in the first place?

By the way, the term "Turing machine" refers to a specific
architecture, and does not describe all machines with infinite state
spaces.  (PDAs are infinite-state devices that can't even recognize
the recursive sets.)  A Turing machine has an infinite read-write tape
with a movable head and only four possible actions (as I recall).
There are very few applications where it is useful to model a computer
as a TM -- infinite or not.
--
David Gudeman

noao!arizona!gudeman

Fri, 05 Nov 1993 04:54:45 GMT
Halting Problem Solved! Film at 11! (Was Re:
David Gudeman:
By the way, the term "Turing machine" refers to a specific
architecture, and does not describe all machines with infinite
state spaces.  ...  A Turing machine has an infinite read-write
tape with a movable head and only four possible actions (as I
recall).  There are very few applications where it is useful to
model a computer as a TM -- infinite or not.

Except that each "cell" on a turing machine tape represents a FSM of
arbitrary complexity.  The "four actions" of a TM are:

(1) do a state transition in the FSM
(2) move to the FSM on the left
(3) move to the FSM on the right
(4) "halt" or "suspend" (transition to an undefined state)

So any FSM is a restricted case of a turing machine, and turing
machines are trivially useful for anything that a FSM is useful for.

Often when people speak of turing machines, they think of one where
every FSM has only two states, and numbers are implemented as strings
of ones.  This particular instance of a turing machine is quite a bit
more limited than turing machines in general.

And while the basic definition of a turing machine only has rules for
a transition to an adjacent FSM you can usually make transitions to
FSMs located arbitrary distances away (as long as the states of the
intervening FSMs are known).  Note that you don't have to enumerate
the states and transitions, as long as each FSM is finite.

The way I understand it, the only kind of machine with an infinite
state space that can't be modeled by a TM is one with non-denumerable
state state space.

Raul Rockwell

Fri, 05 Nov 1993 08:39:27 GMT
Halting Problem Solved! Film at 11! (Was Re:

]David Gudeman:
]   ...  There are very few applications where it is useful to
]   model a computer as a TM -- infinite or not.
]
]Except that each "cell" on a turing machine tape represents a FSM of
]arbitrary complexity...

This is rather opaque.  I can think of several functions to map a
turing machine with a fixed cell to a FSM.  None of them seem
particularly useful.

]So any FSM is a restricted case of a turing machine, and turing
]machines are trivially useful for anything that a FSM is useful for.

Not so.  If an FSM is useful for some purpose, then it would not
necessarily be useful to use a TM (with the added complications) for
the same thing.  It is not useful to build a TM to recognize a regular
expression.

For that matter, I can't think of any application where it is useful
to model a computer as an FSM.  If you are interested in machine
limits, then it seems simpler to begin with a nonfinite machine model.
For example, if you want to answer the question "For what inputs will
this program exceed the machine paramaters?" then the easiest thing to
do is to derive a function of the needed machine resources in terms of
the input (assuming arbitrary resources).  If you were really using an
FSM model then the effect of the resources limits would be pervasive,
making the work much harder.

]The way I understand it, the only kind of machine with an infinite
]state space that can't be modeled by a TM is one with non-denumerable
]state state space.

That depends on what you what you want to model.  If you are only
interested in whether a set can be generated, then this is true.  But
if you are interested in how many operations you need to generate a
given set, then your statement is false.

Besides, just because you _can_ do something a certain way doesn't
mean that is a good way to do it.  It would be silly to define
programming language semantics in terms of a TM.  The Lambda calculus,
the predicate calculus, or a specialized state transition system is
far easier to use.
--
David Gudeman

noao!arizona!gudeman

Sun, 07 Nov 1993 02:56:04 GMT
Halting Problem Solved! Film at 11! (Was Re:

Quote:

>]>[A finite TM is translatable into a FSM.  A FSM has a state space S and a
>]>mapping S -> S.  To see if it halts, pick a starting state, run through the
>]>sequences.  If if goes on the halt state then it halts.  If it ever touches a
>]>state which already occured, it doesn't.  Since there is only a finite number
>]>of states, it takes a finite amount of time to decide (since at most it has
>]>to go through all the states)]
>What machine is going to do this?  If computers are FSM's then you
>only have an FSM to do this, and I can always find a program too big
>to analysis in this way.

I agree, none (plus it would much much too slow- the number of states in real
computers is huge).  The 64K question is can it be done symbolically on the
language source code.  I believe the answer is sometimes.  If you don't have
malloc and you don't have other forms of bignums then it might even be
practicle.  Maybe.  It would be usefull because you could tell at compile time
if you're going to overflow or go past array bounds or run out of stack space.
At any rate, the halting problem proof should not be justification to not at
least research this.  I originally thought that it was because I misunderstood
the halting problem and its scope.

If you're programming in an idealized lisp-like environment, then I guess the
problem starts to approach the actuall halting problem.

Quote:
>By the way, how do you know that the TM is finite in the first place?

Well it's not as defined, but real computers are.  And more importantly, many
times the "functions" or whater the modularity structure in the language in
question is is.

This is not to say that the halting problem is not usefull- it is, but for
fundamental questions of discrete algorithms in idealized environments.

Quote:
>By the way, the term "Turing machine" refers to a specific
>architecture, and does not describe all machines with infinite state
>spaces.  (PDAs are infinite-state devices that can't even recognize
>the recursive sets.)  A Turing machine has an infinite read-write tape
>with a movable head and only four possible actions (as I recall).
>There are very few applications where it is useful to model a computer
>as a TM -- infinite or not.

TMs are used because they can represent any machine with a finite or infinite
(but not continuum) state space (including PDAs).  It's not pretty to
represent real computers on TMs, but it can be done, and that's the point.

Similarly, a FSM as a classification means much more than an EPROM and a
latch.
--

int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}

Wed, 10 Nov 1993 21:57:57 GMT

 Page 1 of 2 [ 18 post ] Go to page: [1] [2]

Relevant Pages