Halting Problem Solved! Film at 11! (Was Re:
Author 
Message 
David Gudem #1 / 18

Halting Problem Solved! Film at 11! (Was Re:
] ]If you want to get theoretical, then you can _theoretically_ keep ]buying tapes... ] ]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) manyworlds ]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 practical objections to it. Your objections do not address the issue 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 


Stephen P Spackm #2 / 18

Halting Problem Solved! Film at 11! (Was Re:
] ]If you want to get theoretical, then you can _theoretically_ keep ]buying tapes... ] ]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) manyworlds ]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 practical objections to it. Your objections do not address the issue 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 address what, perhaps, you thought I was talking about. But I 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. I addressed your comment that I understood to address my argument. 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 


David Gudem #3 / 18

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 unboundedstate 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 


David Gottn #4 / 18

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!autotrol!younam 12500 North Washington Street (303) 2522321 Denver, CO 802412404

Tue, 26 Oct 1993 04:54:01 GMT 


Stephen P Spackm #5 / 18

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. 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 unboundedstate 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 nonobvious 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 


Stephen P Spackm #6 / 18

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 nonrealisable 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 


Raul Rockwe #7 / 18

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 


Chris Tor #8 / 18

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 whoeverstartedthis intended to ask. That is, 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'); read(v); 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'.  InRealLife: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427)

Tue, 26 Oct 1993 22:33:37 GMT 


David Gottn #9 / 18

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 nonrealisable 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!autotrol!younam 12500 North Washington Street (303) 2522321 Denver, CO 802412404

Fri, 29 Oct 1993 12:13:10 GMT 


David Gudem #10 / 18

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 infinitestate devices that can't even recognize the recursive sets.) A Turing machine has an infinite readwrite 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 


Raul Rockwe #11 / 18

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 readwrite 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 nondenumerable state state space. Raul Rockwell

Fri, 05 Nov 1993 08:39:27 GMT 


David Gudem #12 / 18

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 nondenumerable ]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 


Joseph All #13 / 18

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 lisplike 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 infinitestate devices that can't even recognize >the recursive sets.) A Turing machine has an infinite readwrite 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+p80;p=2*a[p])for(z=9;z;)q=3&(r=time(0) +r*57)/7,q=q?q1?q2?1p%79?1:0:p%7977?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[q1]]);}

Wed, 10 Nov 1993 21:57:57 GMT 


Page 1 of 2

[ 18 post ] 

Go to page:
[1]
[2] 
