Re: Release of RosAsm V.2.025a
- From: Herbert Kleebauer <klee@xxxxxxxxx>
- Date: Tue, 04 Oct 2005 17:02:08 +0200
"randyhyde@xxxxxxxxxxxxx" 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).
.
- References:
- Re: Release of RosAsm V.2.025a
- From: Beth
- Re: Release of RosAsm V.2.025a
- From: Herbert Kleebauer
- Re: Release of RosAsm V.2.025a
- From: randyhyde@xxxxxxxxxxxxx
- Re: Release of RosAsm V.2.025a
- Prev by Date: Re: Theoretical Computer Science and Disassemblers
- Next by Date: Re: Release of RosAsm V.2.025a
- Previous by thread: Re: Release of RosAsm V.2.025a
- Next by thread: Re: Release of RosAsm V.2.025a
- Index(es):
Relevant Pages
|
