From: Herbert Kleebauer on 25 Sep 2005 09:58 Phil Carmody wrote: > > > Wolfgang has spoken! The world of computer science stand up and take > > notice! It doesn't matter that some *incredibly* brilliant minds have > > mathematically proven that the "halting problem" reduces to the problem > > of determining whether a byte in memory is code or date (that is, > > they've proven that the problem of disassembly is an undecidable > > problem). > 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". Randy says, creating a perfect disassembler is equivalent to solving the halting problem (I don't know whether this is true, but let's assume it is true) and therefore it is impossible to write a perfect disassembler. And that simple is wrong. 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. So this is the proof, that you can write a perfect disassembler for a closed finite computer system (which means for any real existing computer system). Now that we know that we can write it, we have to try to implement a version which does it's job in an acceptable time and is pretty close to the theoretical possible perfect version. That's similar to strong encryption. We can easily break the encryption by a brute force method (theoretical but not in an acceptable time, which means in time our universe will exist). But because we know that theoretical we can break the code there is many ongoing research to to find algorithm to break the encryption in an acceptable time. Would you also say, that this research is also a waste of time and resources, as you say about finding an algorithm for a perfect disassembler?
From: Paul Dunn on 25 Sep 2005 10:22 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. Isn't this something like the problem for calculating the mandelbrot set? For each coordinate on the plane, the calculation required will either tend towards zero, or towards infinity. Given an infinite number of iterations, the result can be determined to a level of complete accuracy. Unfortunately, an infinite number of iterations requires an infinite amount of time, so an approximation has to be accepted at a maximum level of iterations. Seems to me that this is the problem here - do you have enough time to determine with 100% accuracy that the machine has halted? If an external agency, such as an interrupt, will revive the machine then you have to determine when that agency will intervene. If you don't have that knowledge, then you cannot solve the problem short of actually waiting as long as is necessary - which may be minutes, may be years, might be never. Am I close?
From: Phil Carmody on 25 Sep 2005 10:08 Herbert Kleebauer <klee(a)unibwm.de> writes: > Phil Carmody wrote: > > > > > Wolfgang has spoken! The world of computer science stand up and take > > > notice! It doesn't matter that some *incredibly* brilliant minds have > > > mathematically proven that the "halting problem" reduces to the problem > > > of determining whether a byte in memory is code or date (that is, > > > they've proven that the problem of disassembly is an undecidable > > > problem). > > > 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". > Randy says, creating a perfect disassembler is equivalent to solving > the halting problem (I don't know whether this is true, but let's > assume it is true) and therefore it is impossible to write a perfect > disassembler. And that simple is wrong. 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. So this is the proof, that > you can write a perfect disassembler for a closed finite computer > system (which means for any real existing computer system). Now that > we know that we can write it, we have to try to implement a version > which does it's job in an acceptable time and is pretty close to the > theoretical possible perfect version. That's similar to strong encryption. > We can easily break the encryption by a brute force method (theoretical > but not in an acceptable time, which means in time our universe will > exist). But because we know that theoretical we can break the code > there is many ongoing research to to find algorithm to break the > encryption in an acceptable time. Would you also say, that this > research is also a waste of time and resources, as you say about > finding an algorithm for a perfect disassembler? It's hard to know where to snip the important context where you demonstrate that you've really not thought about things enough from the unimportant context that demonstrates that you've really not thought about things enough, so I've left it all in. Anyway, you've really not thought about things enough. 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. I'll get you started - 0, 1, 2 ... Good luck. Phil -- If a religion is defined to be a system of ideas that contains unprovable statements, then Godel taught us that mathematics is not only a religion, it is the only religion that can prove itself to be one. -- John Barrow
From: randyhyde@earthlink.net on 25 Sep 2005 17:48 Charles A. Crayne wrote: > > :"what were you thinking?" > > I was thinking of the Wikipedia article to which you referred us for > information about the "halting problem", from which I quote: > > "The undecidability of the halting problem relies on the fact that > algorithms are assumed to have potentially infinite storage: at any one > time they can only store finitely many things, but they can always store > more and they never run out of memory. However, computers that actually > exist are not equivalent to a Turing machine but instead to a linear > bounded automaton, as their memory and external storage of a machine is > limited. In this case, the halting problem for programs running on that > machine can be solved with a very simple general algorithm" Of course, the "simple" (arguable) general algorithm, as another poster wrote, is intractible. > > Since the "halting problem" can be solved on real machines, then it > obviously does not impair the ability to write a 'perfect' disassembler. Unless, of course, you want to produce a solution in a reasonable amount of time (like within your lifetime). Cheers, Randy Hyde
From: randyhyde@earthlink.net on 25 Sep 2005 17:52
Betov wrote: > > Hmmm... > > MASM has had far more developers associated with it than RosAsm has. > > MASM is not one of the actual Assembler, and i do not > even consider it, in the above. MASM is virtually dead. As usual, when the facts get in the way of your claims, you stick your head in the sand (like the proverbial ostrich) and ignore the facts. > > > For that matter, FASM has had input from *lots* > > of different people. > > Thomasz never accepted _any_ help of any kind. Hmmm.. I don't hang around the FASM board *that* much, but the time I've spent there I've gotten a completely different impression. Oh well, whatever you say... > When he > is pointed to a bug, with the solution written, he does > not even say "thanks". At least he doesn't go around claiming "it's not a bug" or modifying the assembler to emit weird error messages rather than fixing the bug. :-) Cheers, Randy Hyde |