Author: Uri Blass
Date: 17:06:24 01/31/06
Go up one level in this thread
On January 31, 2006 at 19:50:59, Dann Corbit wrote: >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. I can write down simple instructions to translate exe file to higher language and the only problem is that my algorithm is too slow. My instructions are: 1)Write all the possible programs in the higher language when the order is smaller program first and if 2 programs are of the same size order them by laxisographic order. 2)translate every program to exe file by all compilers. If you find that the exe file is identical stop otherwise continue. The question is not if it is possible to write instructions to do it in paper but if it is possible to have instructions to do it fast enough. time of O(n^2) when n is the size of the exe file is good enough. O(2^n) is not good for practical solution and my solution has complexity of O(a^n) when a is the number of symbols that you can use in the program. 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.