Author: Dann Corbit
Date: 16:50:59 01/31/06
Go up one level in this thread
On January 31, 2006 at 18:25:11, Uri Blass wrote: >On January 31, 2006 at 17:52:18, Dann Corbit wrote: > >>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. > >Note that I used the word *tool* and not the word *program*. >Note that I did not claim that it is possible to write a program that can check >if another program halt and it is clear to me that it is impossible. > >It was proved that no turing machine can solve the problem if some turing >machine is going to halt but it was not proved that the problem cannot be solved >by something else that is not turing machine. > >I understood the basic idea that is the following(replacing the word turing >machine by a program in C). > >Imagine that there is a program in C that can check if another program in C >stops when it gets some input. > >It means that you can write a program in C that get an input that is another C >program and input that it gets and stop only if that program does not stop on >the input. > >Now imagine that the program get itself as an input(twice one as the program to >check and once as the input that it gets). > >If the program stops then it means that the program does not stop and the >opposite and we get contradiction. > >Note that this proof is based on the assumption that the program use the >language of itself. > >Some tool may use more complicated language so the proof does not prove that it >is impossible to build a tool that can check if C program stops. Can you write down the instructions to do it on a paper? That is an equivalent problem. But the problem is really more theoretical than pragmatic. It is obviously possible to write decompilers that are "good enough to be useful" >>>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 >> > >I will look at it but it does not prove that it is impossible to build a >different tool that is not a computer program in order to translate machine code >to higher language code. It is hard to say something is impossible. Especially to do a specific task. But it is probably impossible to determine if a Turing machine halts and disassemblers are equivalent. On the other hand, it is not pragmatically impossible to build a tool that does what you want and does a pretty good job most of the time. >Of course that tool is going to use a more complex language than the machine >language and I guess that it is going to be again impossible to write a program >in that language in order to translate machine code to C code. Tools do exist that eat binary programs and spit out C code. The glop that they spit out will not look like the original but it can still be useful glop.
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.