Re: Random data cannot be compressed

In article <13t5v1a66l52j9d@xxxxxxxxxxxxxxxxxx>,
tim <TimJ@xxxxxxxxxxxx> wrote:

On Sat, 08 Mar 2008 09:36:17 -0800, Ron Garret wrote:

If it is weaker than a TM, such as a finite state machine,
then the theorem is not applicable.

Yes, it is. The only assumption in the proof is that both machines are
the same. The real result of the halting theorem is not that it is
impossible to tell if a TM halts. The real result is that in order to
tell if a machine M halts you need a machine that is strictly more
powerful than M. The TM result is simply a special case of this more
general result, since there is no machine more powerful than a TM.

You must have seen a different proof than me.

See http://www.flownet.com/ron/chaitin.html at the bottom of the page.

Note that the proof makes no reference to the computational model
actually being used. The only requirement is that the programs H and B
run on the same machine.

To determine whether a state machine will terminate you only need a
slightly larger state machine.

That's right. And to determine whether *that* one terminates you need a
slightly larger one yet. And to determine if *that* one terminates...
and then eventually (somewhere before you get to about 140 bits as it
happens) you run out of universe.

Depending on how long the program takes to
start looping or to terminate, you may also need lots of time.

The operative word being "lots." Once N exceeds 2^140 or so it will
take more time than has existed or will exist in this universe.

Turing's theorem is not relevant.

Maybe not, but the proof of Turing's theorem certainly is. That's what
shows that you need an ever-growing tower of FSAs -- and hence an
ever-increasing amount of time -- to compute whether an FSA halts.
(Granted, Turing never actually drew this conclusion, but it's a pretty
obvious corollary. Or at least it seems obvious to me. But I suppose
it's possible that this is a major breakthrough.)

Over and out.

See ya.

rg
.

Relevant Pages

  • Re: Olcott is cured of CrackPottery! (Halting Problem)
    ... >>computer program that checks whether any given computer program ... >>investigation terminates, have your new program go into an infinite ... >>tell if its input program halts and do the opposite. ... So you admit that the argument as stated by Chaitin does not work? ...
    (sci.logic)
  • Re: Olcott is cured of CrackPottery! (Halting Problem)
    ... >>computer program that checks whether any given computer program ... >>investigation terminates, have your new program go into an infinite ... >>tell if its input program halts and do the opposite. ... So you admit that the argument as stated by Chaitin does not work? ...
    (comp.theory)