Release of RosAsm V.2.025a
in [ASM]
|
From: randyhyde@earthlink.net on 4 Oct 2005 10:47 Charles A. Crayne wrote: > > Although I do believe the above claim, I am not the originator of it -- I > am merely reporting the claims made by the reference which you provided: My apologies. Wikipedia is clearly giving some wrong impressions here. Cheers, Randy Hyde
From: randyhyde@earthlink.net on 4 Oct 2005 10:56 Guga wrote: > > Ok...but then, how the processor identifies what is code and what is > data during loading the file ? Well, the processor "identifies" code by executing it. That is, by pointing the IP at the instruction. However, note that some actual instructions in a program may *never* execute. Herein lies another problem with the "perfect" disassembler -- does the perfect disassembler actually disassemble all the code the original user wrote, or does it only disassemble that code which can execute? One has to be careful with how they answer this question. After all, "code" could be data in one part of the program that gets moved to a different location and executed in that different location. A "reasonable" disassembler would disassemble the "code as data" as machine instructions, just as they appear in the original source file. > If as you say, only humans can interpret > what is data and what is code (using the examples of the halting > problem), how the processor never halts when finding those specific > situations ? The whole point is that the program being analyzed may *not* halt. That's what the halting program is trying to determine! And the best known way to solve the halting problem is via emulation. But if you emulate an infinite loop (or other non-halting construct), the emulation (that is, the halting program) never stops. > > If the program works perfectly and yet it contains the "undeciable" > code/data diferenciatinos, how it never hangs ? The original program isn't undecidable. It's the *halting* problem that is undecidable. The implementation of the halting program may certainly hang if the program under test would hang on the given input. > > I mean, if the processor itself have no problems identifying this, why > an disassembler (Assuming it to reproduce the same steps as what the > processor should do) is not possible ? The processor doesn't "identify" this. The processor just keeps executing instructions over and over again. If the original program under test contains an infinite loop, the processor continues executing those statements in that loop, completely oblivious to the fact that the program will never halt. > > The processor only distinguishs when the app is running ? If tis that > it, then we can assume that when a program don´t run, the internal > data can be anything...i mean, it don´t matter at all, because the > processor didn´t actually "saw" the internal contents (dat) yet. Again, you're assuming that the processor is aware of things that it is not. It just executes instructions. The fact that those instructions are infinitely repetitive is not something the CPU is aware of. > > And, if the distinguish can be retrieved only when the app is running, > shouldn´t a debugger mixed with an disassembler could solve this kind > of problem ? A debugger combined with a disassembler is certainly a good tool for disassembling certain types of programs. That's why, for example, that IDAPro includes a built-in debugger so you can do dynamic, in addition to static, analysis of the code you're trying to disassemble. But the disassembler cannot "operate" the debugger and use (all) the information gleaned from the debugger to direct the disassembler. This is another case of Godel's incompleteness theorem at work. Cheers, Randy Hyde
From: Herbert Kleebauer on 4 Oct 2005 11:02 "randyhyde(a)earthlink.net" wrote: > Herbert Kleebauer wrote: > > We have an algorithm A which is feed with an input I (note, > > the input is given, no randomness, no interrupts) and > > we want an other algorithm HALT(A,I) which tells us, whether > > A(I) will halt or not. Now the theorem says, we can't find > > a HALT() which does this for any (A,I). > > Actually, it says for *all* (A, I). And what is the difference between "any" and "all"? > > On the other side, > > it is trivial to find a HALT() which works for any algorithm A > > which can be implemented on a finite system. So the final > > content of the theorem is: > > Technically, it is trivial to determine whether any algorithm A halts. > By definition, all "algorithms" halt. An "algorithm" is a sequence of > steps that executes and guarantees to halt, producing an answer. A > "procedure" is a sequence of steps that *may* produce an answer, but is > not guaranteed to halt. Therefore, the halting problem basically is the > process of differentiating algorithms from procedures. From wikipedia: Some writers restrict the definition of algorithm to procedures that eventually finish. Others include procedures that could run forever without stopping, arguing that some entity may be required to carry out such permanent tasks. Seems, if you are short on arguments in the main topic, you try to move the discussion to some unimportant formal definition. > > There is at least one algorithm/input pair for which it is > > impossible to decide whether it halts or not, > > Well, substitute "procedure" for "algorithm" and this is correct. Well, if you prefer it, I have no problem with this. > > but this is an > > algorithm which only can be implemented on a system with > > an infinite amount of resources. > > Wrong. > The amount of resources has nothing to do with it. > All algorithms (that is, that are guaranteed to halt and produce an > answer) use a finite number of resources. The proof of this is quite > simple. Accessing a "resource" takes at least one computational step > (that is, a finite amount of time). If a program attempted to access an > infinite number of resources it would never halt. A few lines above you have replaced "algorithm" by "procedure" and now you still claim it's wrong because in your definition of algorithm it has to halt. How can you argue about the definition of algorithm when you already have replaced it by procedure? Not very logical. > I think this is a fundamental misconception that many people around > here have. The fact that any given program is finite does *not* imply > that we can determine whether it halts. Nobody said this. But if the resources which the program needs are finite, then it is trivial to decide whether the program halts or not. > > So, if there is any connection between the halting problem > > and disassembling code, then the halting theorem says us: > > If you don't try to disassemble a program which ONLY runs > > on a system with infinite resources, then there is absolutely > > no problem as long as the halting theorem is concerned. So I > > really don't understand about what Randy is talking here. > > Your understanding is incorrect. > The halting program (or a disassembler) will use a finite number of > resources. The input program uses a finite number of resources. Any > program that uses an infinite number of resources will never halt (even > if such resources were available). Seems your understanding is incorrect. You are correct, that any program which USES an infinite number of resources will never halt. Also, for a program which only can use a finite number of resource we always can decide whether it will halt or not. The only problem are programs which CAN use a infinite number of resources. For some of this programs we can't decide whether they will halt or not. Therefore for any program running on an existing (and therefore finite) digital system which is closed (no external interface) we can decide whether it will halt or not. > I think that Chuck Crayne has confused a lot of people by attempting to > claim that these theorems only apply to infinite machines. The > misconception he has created is unfortunate. I should have caught on to > how this knowledge was being misused earlier. I only see you and Beth confused. > But more basically, perfect disassembly implies that every instruction > that was an instruction in the original code is an instruction in the > disassembled code; and every data item that was a data item in the > original code is a data item in the disassembled source. Such a > disassembler cannot be written that automatically does this, and does > this for all inputs (halting, of course). A byte of the binary code isn't either code (exclusive) or data (like a program is halting or not). It can be code, it can be data, it can be code and data or nothing of both (I already gave you an example in my last posting). So even if you are able to decide for each byte which of the four cases is true, you will not be able to write a "perfect" disassembler which always will generate a source which you can then reassemble with a different org statement (and the program still works).
From: Alex McDonald on 4 Oct 2005 13:24 wolfgang kern wrote: > Alex McDonald wrote: > > | > | > .. Show me the border of the universe ... > | > | It is possible for a space to be finite yet unbounded. > | > | Consider the surface of a sphere, for example. > > | > I can't see 'space' on a 'surface' without a Y-direction ;) > | Z direction. > :) yes. > > | > 'flat folks' on a sphere will find a limited environment > | > by just travel straight and reaching the start point again. > > | Yes. The surface of sphere is a 3 dimensional finite yet unbounded > | (edgeless) 2 dimensional space. It's difficult to imagine, but a > | hyper-sphere (a 4 dimensional sphere) is a finite yet unbounded 3 > | dimensional space for beings like us. > > Wouldn't this mean that we could light our back if we pointed > with an ideal sharp laser-beam in straight forward direction? ;) > I can thoroughly recommend http://www.astro.ucla.edu/~wright/cosmolog.htm for a good, relatively math light introduction to the subject. If the universe is geometrically a sphere and is unbounded and finite, then shooting light out of a laser would return it to its starting point after travelling the circumference of the sphere. However, it's thought that the "size" (and hence the circumference) of the universe is much larger (about 80billion light years) than the observable universe, which is about 13billion light years across; the ray would never return, given that the observable universe gets a second older (and hence a second bigger) for every second that the light ray travels. You might argue that it should, if it's a sphere; that's OK, because the minimum transit time will be several tens of billions of years, and neither of us will be around to collect the bet. I'll not loose sleep over it. However, consider Olber's paradox (see here http://www.astro.ucla.edu/~wright/cosmology_faq.html#OP). The sky is dark at night, not full of starlight at every point. Also see http://www.astro.ucla.edu/~wright/cosmology_faq.html#RB for an explanation of why the universe is thought to be much bigger than the observable universe. -- Regards Alex McDonald
From: Phil Carmody on 9 Oct 2005 15:35
Herbert Kleebauer <klee(a)unibwm.de> writes: > 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 ? No. Does it look like I claim that? Your pathetic attempt at a straw man argument has failed miserably. Again. > 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. No. Does it look like I claim that? Your other pathetic attempt at a straw man argument has failed miserably. Yet again. > Or do you simple not understand the difference between the theoretical > proof that a solution exists and the inability to find this solution. I understand completely. Now start counting up to N, you blathering fool. 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 |