Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!news.stack.nl!.POSTED!not-for-mail From: Willem Newsgroups: comp.compression Subject: Re: Kolmogorov compression? Date: Sun, 12 May 2013 20:17:33 +0000 (UTC) Organization: Stack Usenet News Service Lines: 27 Message-ID: References: <001faf1b-28af-4e93-b64a-17d42642bb24@googlegroups.com> <0f889114-ded8-4ac2-a71a-16b3c4f2d8ef@googlegroups.com> <2655b3b3-21d6-4621-97ce-14a7ff1fd39f@googlegroups.com> NNTP-Posting-Host: turtle.stack.nl Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: mud.stack.nl 1368389853 47642 2001:610:1108:5010::132 (12 May 2013 20:17:33 GMT) X-Complaints-To: abuse@stack.nl NNTP-Posting-Date: Sun, 12 May 2013 20:17:33 +0000 (UTC) User-Agent: slrn/0.9.9p1 (FreeBSD) Xref: csiph.com comp.compression:1940 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