From: Phil Carmody on
"randyhyde(a)earthlink.net" <randyhyde(a)earthlink.net> writes:
> wolfgang kern wrote:
> >
> > So for new readers I state it one more time:
> > "the halting problem does not apply to disassembling"
> > (see discussions on it in the history of ALA-posts).
>
> Wolfgang has spoken! The world of computer science stand up and take
> notice! It doesn't matter that some *incredibly* brilliant minds have
> mathematically proven that the "halting problem" reduces to the problem
> of determining whether a byte in memory is code or date (that is,
> they've proven that the problem of disassembly is an undecidable
> problem).
>
> So do go back and read Wolfgang's posts of old, where he's made this
> claim in the past! It appears in a usenet newsgroup! It *must*,
> therefore, be true!
>
> To Wolfgang: it has been nearly a year since *you* claimed that your
> work on a disassembler would yield a perfect disassembler program.
> Where's the solution? We're all still waiting for you to shake the
> foundations of theoretical computer science!

Mathematically (and I'm a mathematician at heart), you're correct.

However, if you were to modify Wolfgang's (incorrect) statement to
'The halting problem does not apply to disassembling the output
of tools such as compilers', then it would almost certainly be
correct. Getting rid of (the implicit) "arbitrary", does wonders.

However, if you were to modify things Betov and Hutch say, then
you'd probably get correct things too, so this proves nothing.


Phil
--
If a religion is defined to be a system of ideas that contains unprovable
statements, then Godel taught us that mathematics is not only a religion, it
is the only religion that can prove itself to be one. -- John Barrow
From: Phil Carmody on
"Charles A. Crayne" <ccrayne(a)crayne.org> writes:
> On 24 Sep 2005 15:31:26 -0700
> "randyhyde(a)earthlink.net" <randyhyde(a)earthlink.net> wrote:
>
> :"what were you thinking?"
>
> I was thinking of the Wikipedia article to which you referred us for
> information about the "halting problem", from which I quote:
>
> "The undecidability of the halting problem relies on the fact that
> algorithms are assumed to have potentially infinite storage: at any one
> time they can only store finitely many things, but they can always store
> more and they never run out of memory. However, computers that actually
> exist are not equivalent to a Turing machine but instead to a linear
> bounded automaton, as their memory and external storage of a machine is
> limited. In this case, the halting problem for programs running on that
> machine can be solved with a very simple general algorithm"
>
> Since the "halting problem" can be solved on real machines, then

You're living in a universe where 2^34359738368, or more, quanta
of time is an acceptible delay for an answer. If the machine
has a hard disk, then you're looking at potential delays of
2^1000000000000 quanta. This is not the real world, Chuck.
These are not 'real machines'. There simply ain't that number
of ticks in the universe.

You have conflated "can be solved with a very simple algorithm"
with "can be solved very simply".

> it
> obviously does not impair the ability to write a 'perfect' disassembler.

As the value of not tends to .

Phil
--
If a religion is defined to be a system of ideas that contains unprovable
statements, then Godel taught us that mathematics is not only a religion, it
is the only religion that can prove itself to be one. -- John Barrow
From: wolfgang kern on

Charles A. Crayne answered <randyhyde(a)earthlink.net> :

| :"what were you thinking?"
|
| I was thinking of the Wikipedia article to which you referred us for
| information about the "halting problem", from which I quote:
|
| "The undecidability of the halting problem relies on the fact that
| algorithms are assumed to have potentially infinite storage: at any one
| time they can only store finitely many things, but they can always store
| more and they never run out of memory. However, computers that actually
| exist are not equivalent to a Turing machine but instead to a linear
| bounded automaton, as their memory and external storage of a machine is
| limited. In this case, the halting problem for programs running on that
| machine can be solved with a very simple general algorithm"

| Since the "halting problem" can be solved on real machines, then it
| obviously does not impair the ability to write a 'perfect' disassembler.

Hi Chuck,

Randy's theory is based on programmed indeterminacy,
but also this can be detected in an automated process.

Only because x86 ASM-syntax is incomplete determined by definition
(it may compile the disassembled source different to the original bytes),
I replaced the 'perfect' (the theoretical ideal) with 'complete'.

The functionality will not change, even if instruction were part of
self-modifying code, but there might be a few bytes look different to
the original (ie: 8B/89).

And Randy will remain in my killfile, ... for more than one reason.

__
wolfgang



From: wolfgang kern on

Phil Carmody answered <randyhyde(a)earthlink.net>:

| > wolfgang kern wrote:
| > >
| > > So for new readers I state it one more time:
| > > "the halting problem does not apply to disassembling"
| > > (see discussions on it in the history of ALA-posts).
| >
| > Wolfgang has spoken! The world of computer science stand up and take
| > notice! It doesn't matter that some *incredibly* brilliant minds have
| > mathematically proven that the "halting problem" reduces to the problem
| > of determining whether a byte in memory is code or date (that is,
| > they've proven that the problem of disassembly is an undecidable
| > problem).
| >
| > So do go back and read Wolfgang's posts of old, where he's made this
| > claim in the past! It appears in a usenet newsgroup! It *must*,
| > therefore, be true!

| > To Wolfgang: it has been nearly a year since *you* claimed that your
| > work on a disassembler would yield a perfect disassembler program.
| > Where's the solution? We're all still waiting for you to shake the
| > foundations of theoretical computer science!

To the unseen:
just to get rid of your theoretical 'perfect'-ideal claims,
I named it the 'complete' disassembling code analyser.
Sell many books, collect money and place an order (but pay in advance)
and then wait until I'm willing to have business with weird folks.


| Mathematically (and I'm a mathematician at heart), you're correct.

| However, if you were to modify Wolfgang's (incorrect) statement to
| 'The halting problem does not apply to disassembling the output
| of tools such as compilers', then it would almost certainly be
| correct. Getting rid of (the implicit) "arbitrary", does wonders.

Yes Phil, my statement wasn't complete at all.
My solution for a static code analysis implies 'endless loop'- and
indeterminancy -detection, so it will report situations like this as two
more conditions (undetermined and/or endless) for a program-path end.

So even not 'perfect' in terms of theory,
but at least 'complete' to make sense in the practice.

__
wolfgang


From: Betov on
Phil Carmody <thefatphil_demunged(a)yahoo.co.uk> ?crivait
news:87wtl5pp8k.fsf(a)nonospaz.fatphil.org:

> "randyhyde(a)earthlink.net" <randyhyde(a)earthlink.net> writes:
>> wolfgang kern wrote:
>> >
>> > So for new readers I state it one more time:
>> > "the halting problem does not apply to disassembling"
>> > (see discussions on it in the history of ALA-posts).
>>
>> Wolfgang has spoken! The world of computer science stand up and take
>> notice! It doesn't matter that some *incredibly* brilliant minds have
>> mathematically proven that the "halting problem" reduces to the
problem
>> of determining whether a byte in memory is code or date (that is,
>> they've proven that the problem of disassembly is an undecidable
>> problem).
>>
>> So do go back and read Wolfgang's posts of old, where he's made this
>> claim in the past! It appears in a usenet newsgroup! It *must*,
>> therefore, be true!
>>
>> To Wolfgang: it has been nearly a year since *you* claimed that your
>> work on a disassembler would yield a perfect disassembler program.
>> Where's the solution? We're all still waiting for you to shake the
>> foundations of theoretical computer science!
>
> Mathematically (and I'm a mathematician at heart), you're correct.

There is nothing particualry "Mathematically correct",
in the fact of discribing a problem the wrong way.


> However, if you were to modify Wolfgang's (incorrect) statement to
> 'The halting problem does not apply to disassembling the output
> of tools such as compilers', then it would almost certainly be
> correct. Getting rid of (the implicit) "arbitrary", does wonders.

Where is the Disassembler that you have wrote?


> However, if you were to modify things Betov and Hutch say, then
> you'd probably get correct things too, so this proves nothing.

Maybe, but what is 100% guaranted by this sentence is
that you are a small troll with a big mouth.


Betov.

< http://rosasm.org >