Release of RosAsm V.2.025a
in [ASM]
|
From: Herbert Kleebauer on 25 Sep 2005 18:08 Paul Dunn wrote: > Herbert Kleebauer wrote: > > > If you have an closed system > > with a finite number of states (N), then it is trivial to solve the > > halting problem for such a system: simulate N steps, then either the > > system has halted or it never will halt. > Seems to me that this is the problem here - do you have enough time to > determine with 100% accuracy that the machine has halted? It is a finite amount of time, that's all that matter. For a system with a 10 Gbyte HD you get about 10^11 bit (including RAM and HW FlipFlops). All you have to do is, to simulate 2^(10^11) steps. This is practical impossible but theoretical trivial. > If an external > agency, such as an interrupt, It is a closed system, so no external interrupts.
From: Herbert Kleebauer on 25 Sep 2005 18:08 Phil Carmody wrote: > Herbert Kleebauer <klee(a)unibwm.de> writes: > > Phil Carmody wrote: > > > Mathematically (and I'm a mathematician at heart), you're correct. > > > > If you are a "mathematician at heart", then you should know the > > difference between "theoretical impossible" and "practical impossible". > > If you insist on being publically hit with a clue-stick - work out > what N might be, and quit posting things that demonstrate that > you've not thought about things enough until you've: > a) counted up to N (write a program, in assembly if you like) > and > b) thought about things enough. Do you really claim that there exist a (closed) digital system for which no N exist, so that the number of possible different states is <N ? Or do you claim that it is wrong, that if the number of possible different states is <N, that then after N simulation steps the system either has halted or will never halt. Or do you simple not understand the difference between the theoretical proof that a solution exists and the inability to find this solution.
From: randyhyde@earthlink.net on 27 Sep 2005 12:44 Herbert Kleebauer wrote: > > Or do you simple not understand the difference between the theoretical > proof that a solution exists and the inability to find this solution. I think the point that Phil is making is that although, in theory, all real computer systems have a finite number of states, and therefore you can enumerate all possible combinations of those states, the number of states is so high that for all practical purposes it is impossible to enumerate them. Also note one other thing (as this relates to disassemblers), in order to enumerate all those possible states, and recognize which collections of states correspond to halting (or non-halting) programs, you need a *bigger* machine to do the recognition. IOW, it may be theoretically possible to create a program that will recognize all programs that can halt on an x86 CPU, but you certainly aren't going to be able to *run* that program on an x86 CPU, as that program requires more states that are available on the x86. Cheers, Randy Hyde
From: Charles A. Crayne on 27 Sep 2005 17:32 On 27 Sep 2005 09:44:49 -0700 "randyhyde(a)earthlink.net" <randyhyde(a)earthlink.net> wrote: :IOW, it may be theoretically :possible to create a program that will recognize all programs that can :halt on an x86 CPU, but you certainly aren't going to be able to *run* :that program on an x86 CPU, as that program requires more states that :are available on the x86. Your conclusion that one cannot emulate an x86 CPU in a program which runs on an x86 CPU will come as a great surprise to those who have already done so. -- Chuck
From: randyhyde@earthlink.net on 28 Sep 2005 11:53
Charles A. Crayne wrote: > > Your conclusion that one cannot emulate an x86 CPU in a program which runs > on an x86 CPU will come as a great surprise to those who have already done > so. > > -- Chuck There is a big difference between "a" program and "any" program. Cheers, Randy Hyde |