Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1940

Re: Kolmogorov compression?

Show all headers | View raw

Thomas Richter wrote:
) On 10.05.2013 00:52, jacko wrote:
)> Ignore this man, he's being an obtuse idiot. Get the maximal considered state size X, and reserve 2*X bits.
)
) Your error is that the state of a Turing machine consists of its 
) internal state, plus the state of its tape, which is infinite. And thus, 
) the overall size of the state of a Turing machine is not finite. Thus, 
) you cannot detect cycles of a Turing machine this way.

His point is that the halting problem can be easily sidestepped by limiting
the length of the tape, which means it's not a true Turing machine, but
no existing computer is a true Turing machine in that exact same sense.

In fact, it's quite easy to construct a compressor that just enumerates
through all possible input programs, running them for a finite amount of
time in a sandbox, and to output the one that produces the desired output.
The only problem is that the runtime of the compressor will be longer
than the lifespan of the universe for any interesting data sizes.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Kolmogorov compression? Industrial One <industrial_one@hotmail.com> - 2013-04-29 12:14 -0700
  Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-04-29 23:03 +0200
    Re: Kolmogorov compression? Industrial One <industrial_one@hotmail.com> - 2013-04-29 14:30 -0700
      Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-04-30 00:28 +0200
      Re: Kolmogorov compression? "George Johnson" <matrix29@charter.net> - 2013-04-29 22:41 -0400
  Re: Kolmogorov compression? Ernst <Ernst_Berg@sbcglobal.net> - 2013-05-01 19:32 -0700
    Re: Kolmogorov compression? jacko <jackokring@gmail.com> - 2013-05-08 18:34 -0700
      Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-05-09 21:17 +0200
        Re: Kolmogorov compression? jacko <jackokring@gmail.com> - 2013-05-09 15:52 -0700
          Re: Kolmogorov compression? jacko <jackokring@gmail.com> - 2013-05-09 17:08 -0700
          Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-05-10 11:34 +0200
            Re: Kolmogorov compression? Willem <willem@turtle.stack.nl> - 2013-05-12 20:17 +0000
              Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-05-12 22:36 +0200
                Re: Kolmogorov compression? Industrial One <industrial_one@hotmail.com> - 2013-05-12 15:45 -0700
                Re: Kolmogorov compression? "George Johnson" <matrix29@charter.net> - 2013-05-12 19:37 -0400
                Re: Kolmogorov compression? Thomas Richter <thor@math.tu-berlin.de> - 2013-05-13 08:48 +0200
  Re: Kolmogorov compression? Ernst <Ernst_Berg@sbcglobal.net> - 2013-05-15 11:04 -0700

csiph-web