Author: Uri Blass
Date: 15:25:11 01/31/06
Go up one level in this thread
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. > >>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. 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. Uri
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.