Prev: Fairness: Where can it be better handled?
Next: Artificial Intelligence Discovery Generates Software Extensions Tied to Math
From: tchow on 14 May 2010 11:25 In article <852jm9FopcU1(a)mid.individual.net>, Tim Frink <plfriko(a)yahoo.de> wrote: >But what about reallife 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 finitestate machines is decidable, yes. However, it's worth pointing out a slight pitfall here. One might be tempted to argue that since reallife systems can be "reasonably" modeled as finitestate machines, the halting problem for reallife systems is solvable in practice (ignoring complexity issues). The trouble is that the halting problem for finitestate machines is *not decidable by a finitestate machine*. In other words, if you want to model all reallife systems as finite state machines, then the halting problem for reallife machines is decidable only by an imaginary machine, and not by a reallife 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 finitestate 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 finitestate 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 finitestate camp.  Tim Chow tchowatalumdotmitdotedu The range of our projectileseven ... the artilleryhowever 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 <rdecker(a)hamilton.edu> 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 reallife 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 realworld 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 <plfriko(a)yahoo.de> 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
First

Prev

Next

Last
Pages: 1 2 3 4 5 Prev: Fairness: Where can it be better handled? Next: Artificial Intelligence Discovery Generates Software Extensions Tied to Math 