From: tchow on 14 May 2010 11:25 In article <852jm9FopcU1(a)mid.individual.net>, Tim Frink wrote:>But what about real-life systems such as my Intel Linux box where I >run e.g., C programs? These computer systems can be modeled as finite >state machines where I could (at least in theory) test all possible >program executions, i.e., all possible initial states and all possible >inputs (of course in practice one runs into complexity problems). But >this would mean that the halting problem becomes decidable, right? The halting problem for finite-state machines is decidable, yes. However, it's worth pointing out a slight pitfall here. One might be tempted to argue that since real-life systems can be "reasonably" modeled as finite-state machines, the halting problem for real-life systems is solvable in practice (ignoring complexity issues). The trouble is that the halting problem for finite-state machines is *not decidable by a finite-state machine*. In other words, if you want to model all real-life systems as finite state machines, then the halting problem for real-life machines is decidable only by an imaginary machine, and not by a real-life machine. The reason that people prefer the Turing machine as a model of computation despite its seemingly unrealistic unbounded memory is that it captures the notion of algorithms where there's a clear concept of how to *extrapolate* the algorithm *if* we were given more memory. No finite-state machine is capable of recognizing when a binary string consists of a bunch of zeros followed by an equal number of ones, because no matter how big the machine is there will always be a really long binary string where the number of zeros is too large for the poor finite-state machine to keep track of. But most of us feel intuitively that this is an easy problem and not an "uncomputable" problem because we see how to write a simple program that will solve it, provided that it's given memory proportionate to the problem instance that it's supposed to solve. If you feel this way then you have already defected to the Turing machine camp from the finite-state camp. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences From: Tim Frink on 15 May 2010 07:29 First of all thank you for all your answers.> >> The halting problem for finite machines is decidable by machines with >> exponentially more resources than the ones being modelled. > > Actually, twice as much memory is enough. Why do we need twice as much memory? Once for the N states of the machine to be tested and N states for the testing machine that has to model all these N states? And a practical question: how could a real machine by modeled as a finite state machine? Do all the available resources of the machine have to be modeled or is it sufficient to model all possible states of the available memory into which the machine can run?> > If a machine with N possible states terminates, it must do so after at > most N steps, otherwise it will have entered a loop. So to decide > termination, you just run a copy of the machine and count the number of > steps. If you terminate before N steps, you have proven termination. If > not, you have proven nontermiantion. Why is it sufficient to check just N states? If the machine runs into a loop it may happen that some states are repeated. So, my intuition tells me that the machine could in total visit a multiple of the N states before terminating. And how can the termination of such a program be determined: main(x) { while(x); // repeat when x==1 } In this case I might happen that the input x=1 is provided more than N times to the program. So, nontermination might be wrongly assumed. Tim From: Jym on 16 May 2010 17:31 On Thu, 13 May 2010 18:32:06 +0200, Rick Decker wrote: > On 5/13/10 11:20 AM, Tim Frink wrote: >> Hi, >> >> it is known that the haling problem is not decidable in general. >> >> When I understand it correctly, this is only true if the system where >> the computation is performed is considered to be a turing machine (with >> an infinite number of states and infinitely large variable values). >> >> But what about real-life systems such as my Intel Linux box where I >> run e.g., C programs? These computer systems can be modeled as finite >> state machines where I could (at least in theory) test all possible >> program executions, i.e., all possible initial states and all possible >> inputs (of course in practice one runs into complexity problems). But >> this would mean that the halting problem becomes decidable, right? > Right. The Halting Problem for finite automata is decidable, though > a real-world computer has so many states that it might take *ahem* > a bit of time to decide. To make this a bit more precise: If you have 100 bits, you have 2^100 states. If you run this on a computer around 10GHz (not too bad even these days), you can go through approximately 10^10 different states per second. Going through the 2^100 states of you machine will require a time roughly equal to the age of the universe (give or take 10%)... Now, real computers don't have 100 bits but somewhere around 4GB RAM (that is 2^32 bits !) and around 300GB of hard drive... This, to speak only about personal computers. Not the huge thing used for large computations... -- Hypocoristiquement, Jym. From: Torben �gidius Mogensen on 17 May 2010 05:37 Tim Frink writes: > First of all thank you for all your answers. >> >>> The halting problem for finite machines is decidable by machines with >>> exponentially more resources than the ones being modelled. >> >> Actually, twice as much memory is enough. > > Why do we need twice as much memory? Once for the N states of the machine > to be tested and N states for the testing machine that has to model all > these N states? No, N states for the machine being tested and a counter that tells you if you have been in more than N states (which implies that a state is repeated). If you, for example, have 100 bits of data this is 2^100 states. You need 100 bits for a counter that can count to 2^100, so the counter needs as much space as the state. Torben From: Tim Frink on 17 May 2010 13:47 > If you, for example, have 100 bits of data this is 2^100 states. You> need 100 bits for a counter that can count to 2^100, so the counter > needs as much space as the state. OK, thank you. It would be great if someone could also answer my other questions. ;-) Regards, Tim