From: Tim Frink on 17 May 2010 13:53 > 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%)... But why is it sufficient to go just through all the states? If the program contains loops, some states will be entered multiple times. Hence, more than 2^100 would be entered before possibly finally terminating the program. From: Barb Knox on 17 May 2010 16:15 In article <85de5bF1vaU2(a)mid.individual.net>, Tim Frink wrote: > > 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%)... > > But why is it sufficient to go just through all the states? If the program > contains loops, some states will be entered multiple times. Hence, more > than 2^100 would be entered before possibly finally terminating the > program. A state here represents *everything* that can be different during the computation. For example, there is no external input (such as you used in a previous example). The next state is a deterministic function of the current state. So, once the machine returns to a previous state, it's in a loop forever. -- --------------------------- | BBB b \ Barbara at LivingHistory stop co stop uk | B B aa rrr b | | BBB a a r bbb | Quidquid latine dictum sit, | B B a a r b b | altum videtur. | BBB aa a r bbb | ----------------------------- From: Tim Little on 17 May 2010 21:00 On 2010-05-17, Tim Frink wrote:> But why is it sufficient to go just through all the states? If the > program contains loops, some states will be entered multiple > times. In this discussion we are using the term "state" to include everything relevant to program execution. A deterministic machine that enters the same state twice will loop forever, because every step between the two occurrences will be repeated. E.g. for a finite-tape Turing machine, the overall state includes the sequence of symbols on the tape and the head position as well. That's why the size of the machine state for real computers has to include hard drives and memory as well as CPU registers and so on. Though once you get into multithreaded programs running on CPUs with independently clocked cores, it becomes less reasonable to use a purely deterministic model. There exists the possibility of race conditions depending upon arbitrary small differences in timing. - Tim From: Tim Frink on 18 May 2010 03:33 > In this discussion we are using the term "state" to include everything> relevant to program execution. A deterministic machine that enters the > same state twice will loop forever, because every step between the two > occurrences will be repeated. > > E.g. for a finite-tape Turing machine, the overall state includes the > sequence of symbols on the tape and the head position as well. That's > why the size of the machine state for real computers has to include hard > drives and memory as well as CPU registers and so on. OK, that's clear now. In one of my previous posts, I mentioned a program like this: main(x) { while(x); // repeat when x==1 } Here the termination depends on the input that is unknown. Are such input- dependent programs also considered for the halting problem? I mean here we can only judge if the program terminates when the program input is known. Tim From: Torben �gidius Mogensen on 18 May 2010 09:39 Tim Frink writes: > In one of my previous posts, I mentioned a program like this: > > main(x) > { > while(x); // repeat when x==1 > } > > Here the termination depends on the input that is unknown. Are such input- > dependent programs also considered for the halting problem? I mean here we > can only judge if the program terminates when the program input is known. A variant of the halting problem is "Does this program terminate for all possible inputs?". They are both undecidable for Turing machines (and other Turing-complete language). For a finite automata (with a fixed buound on input size), both are decidable by a larger finite automata, but the actual resources required are larger for the more general question. Both variants are instances of the more general Rice's theorem: Any nontrivial question that you ask about the semantics (input/output function) of programs in a turing-complete language are undecidable. Trivial questions are those that can be answered yes for all programs and those that can be answered no for all programs. Halting is part of the semantics (considering nontermination a special value), so the halting problem is an instance of Rice's theorem. Other instances are: - Is there any input that makes the program return 42? - Will this program return 42 when run with this particular input? - Is the program equivalent to this other program? Torben