Author: Dann Corbit
Date: 14:52:18 01/31/06
Go up one level in this thread
On January 31, 2006 at 17:08:31, Uri Blass wrote: >On January 31, 2006 at 14:22:36, Dann Corbit wrote: > >>On January 28, 2006 at 16:07:15, Uri Blass wrote: >> >>>On January 28, 2006 at 15:54:46, Sebastian Leibnitz wrote: >>> >>>>Look here: >>>> >>>>http://www.program-transformation.org/Transform/AutomaticDecompiler >>> >>>Thanks >>> >>>If I understand correctly it is even not possible to get assembly code of a >>>program automatically and the user need to guess things. >> >>100% correct decompilation is PROVABLY impossible (it has been shown to be >>equivalent to the question "Will the Turing machine halt?") > >I do not understand what is the problem. > >The exe file is a file that has instructions for the program what to do. >Common sense tells me that it should be possible to translate the instruction to >another language(I am not talking about names of variables and names of function >but only about code that does exactly the same thing). > >A problem of translating from english to another language is not impossible to >solve. > >I do not see a reason to believe that it is impossible to solve the problem of >translating exe file to C code that does the same thing. > >I do not see connection to the halting problem. > >Note that even in the halting problem there is no proof that it is impossible to >build a tool that check if a computer program stops. You are quite wrong about that. It has been proven conclusively, and it is not in debate at all. >The only clear thing is that tool cannot be a computer program(otherwise we get >a paradox). > > >I do not know much about computers but I believe that >basically every computer has finite number of states. >Assuming no problem in the machine it is clear that after enough time if the >program does not stop it got the same state again so it will never stop. > >If a computer use memory of 2^30 bits and every bit can be 0 or 1 then it seems >to me that the computer has 2^(2^30) states. > >It is less that 10^1,000,000,000 and if a program does not stop after >10^1,000,000,000 years it will never stop. > >Of course we cannot wait so long but it is clear that the problem if a program >is going to stop is solvable in finite time and the only question seems to be >how much it can reduced. The result about decompilation being equivalent to the halting problem is a very well known result and is found in dozens of separate papers. Here is one of them: http://www.jpbowen.com/pub/enum5-n.pdf >>On the other hand, for specific machines and specific compilers, it is possible >>to write decompilers that are generally helpful most of the time. >> >>You can't turn the hamburger back into the cow, no matter what anyone says. But >>you can figure out things like "What kind of cow was it?" "What part of the cow >>did this come from?" >> >>The comments are gone. The helpful variable names are gone. The code will be >>much larger and will have been rearranged by the compiler. > >I already understood that names of variables and name of function are gone(the >compiler does not need them to translate the code to exe file). >I do not understand why the code has to be larger. Typically, loops are unrolled, among other things. (Do a search for "Duff's device"). The decompiled program will not have to be larger (though usually they are, and the assembly will typically be many times larger). I expect on average that the algorithm loops will be somewhat larger than the original and clearly different almost all of the time.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.