Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Comment author: Anatoly_Vorobey 11 December 2014 04:01:41PM 2 points [-]

There is no such thing as "the shortest program for which the halting property is uncomputable". That property is computable trivially for every possible program. What's uncomputable is always the halting problem for an infinity of programs using one common algorithm.

It is also easy to make up artificial languages in which Kolmogorov complexity is computable for an infinite subset of all possible strings.

You were probably thinking of something else: that there exists a constant L, which depends on the language and a proof system T, such that it's not possible to prove in T that any string has Kolmogorov complexity larger than L. That is true. In particular, this means that there's a limit to lower bounds we can establish, although we don't know what that limit is.

Comment author: V_V 11 December 2014 07:11:34PM *  2 points [-]

There is no such thing as "the shortest program for which the halting property is uncomputable". That property is computable trivially for every possible program.

The halting property is semi-decidable: if a program halts, then you can always trivially prove that it halts, you just need run it. If a program does not halt, then sometimes you can prove that it doesn't halt, and sometimes you can't prove anything.
For any programming language, there exist a length such that you can compute the halting property for all programs shorter than that. At length L_max, there will be program Bad_0, which:

  • Does not halt.
  • Can't be proven not to halt.
  • Doesn't emit any output symbol.
  • It can't be proven that there exist any string of output symbols that it doesn't emit.

You can never prove that any string S has Kolmogorov complexity K if K > L_max, as it would imply that you proved that Bad_0 doesn't halt, or at least doesn't emit any symbol which is not a prefix of S.

Since there are only finitely many strings with complexity up to L_max, we can only compute Kolmogorov complexity, for finitely many strings.

It is also easy to make up artificial languages in which Kolmogorov complexity is computable for an infinite subset of all possible strings.

If the language is Turing-complete I don't think this is possible. If you think that an arbitrary string S has complexity K, how can you prove that there exist no program shorter than K that computes S?

Comment author: gwern 09 December 2014 08:00:48PM *  2 points [-]

There can't be, since KC isn't computable (could be mistaken on that in itself precluding a bounded error).

KC may not be uncomputable in general, but I'm pretty sure that doesn't preclude all possible proofs or constructions*, and it seems odd to say that there is no upper bounds when we have what sure look like such things.

* I have just invented a Scheme-like programming language in which all tokens except numbers are 2 alphanumeric characters long; what is the Kolmogorov complexity of the bitstring '1'? 'Who knows, KC is uncomputable -' Bzzt! The answer is that the KC is exactly 1, since the shortest program which emits the bitstring '1' is a program consisting of the constant '1' which evaluates to '1', which as you can see, is indeed of length 1, and all other programs emitting the bitstring '1' are longer by definition.

Or if you don't like that example, consider taking your favorite language and enumerating all possible programs in length order; consider the outputs of the programs you've just enumerated when evaluated up to the highest available Busy Beaver in steps (to avoid nontermination issues), and the respective lengths of outputs - have you not found the KC for those outputs? If you run gzip over the outputs to get estimated KCs, are those not upper bounds on the actual KCs you proved?

Comment author: V_V 09 December 2014 08:30:50PM *  2 points [-]

Computing upper bounds on on Kolmogorov Complexity is not very difficult: gzip and all the other compression algorithms do it. The difficulty is computing non-trivial lower bounds:
For all programming languages (with a self-terminating encoding), there is a trivial lower bound that doesn't depend on the string. This bound is at least one token.

But there is also a language-dependent constant L_max which is the maximum KC complexity and lower bound on KC complexity that you can compute for any string: L_max is the length of the shortest program for which the halting property is uncomputable ( * ) (which makes L_max is uncomputable as well).
This implies that you can compute the KC complexity only for a finite number of strings.

( * And doesn't provably emit any token)

Comment author: Ander 08 December 2014 07:02:46PM 5 points [-]

I propose a new version of the Turing test: An AI is as smart as a human when it can figure out which new poster on a message board is actually the same person as an old poster who got banned. :)

Comment author: V_V 09 December 2014 11:14:02AM 6 points [-]

I don't think this is actually a difficult problem. Some simple machine learning on word frequencies, bigram frequencies, etc. will be probably enough to solve it.

Comment author: RichardKennaway 08 December 2014 12:13:04PM 10 points [-]

These seem pretty easy to answer even for a non-expert.

It is variously said that we share 99% of our genes with a chimpanzee, 95% of our genes with a random human, and 50% of our genes with a sibling. Explain how these can all be true statements.

Comment author: V_V 08 December 2014 04:44:45PM *  2 points [-]

Non-expert there, but here are my two cents:

we share 99% of our genes with a chimpanzee

If you sequence your DNA and the DNA of a random chimp, and consider only the substrings that can be identified as genes, and measure string similarity between them, you will get a number between 98% and 99%, depending on the choice of string similarity measure (there are many reasonable choices).

95% of our genes with a random human

Never heard that before.

50% of our genes with a sibling

Suppose an unique id tag was attached to all the gene strings in the DNA of each of your parents. Even if the same gene appears in both of your parents, or even if it appears multiple times in the same parent, each instance gets a different id.
Then your parents mate and produce you and your sibling. On average, you and your sibling will share 50% of these gene ids.
Of course, many of these genes with different ids will be identical strings, hence the genetic similarity measured as in the human-chimp case will be > 99.9%.

Comment author: V_V 08 December 2014 04:19:48PM 1 point [-]

This suggests that deep learning is an approach that could be made or is already conceptually general enough to learn everything there is to learn (assuming sufficient time and resources). Thus it could already be used as the base algorithm of a self-optimizing AGI.

The paper is interesting, but I don't think that the authors make this claim or that this claim is suggested by the paper.

Comment author: ThisSpaceAvailable 28 November 2014 06:44:53AM 0 points [-]

That something has a casual influence on something else doesn't mean that doing the first eliminates moral high ground to complain about the second.

Comment author: V_V 28 November 2014 08:03:09AM *  2 points [-]

EY bears part of the responsibility for people learning about the basilisk from RationalWiki, since due to his censorship, they can't (couldn't?) learn about it from LessWrong, where the primary source would have been available.

Comment author: ThisSpaceAvailable 26 November 2014 08:35:36AM *  1 point [-]

If A = RationalWiki might have perhaps misrepresented Roko's basilisk

B = I don't think that EY gets to complain that people learn about it from RationalWiki

C = he has censored any discussion about it on LessWrong for year

The literal denotation of your post is "A, but C -> B", but it seems to me that mentioning A in such close proximity to C -> B is a (perhaps unintentional) Dark Arts way of communicating C -> A.

Comment author: V_V 26 November 2014 10:48:51AM 2 points [-]

C => A might be also true to some extent, although it is hard to tell given that RationalWiki misrepresent lots of things even when good primary sources are available.

My point however was that even if EY might be epistemically right about A, C implies that he has no moral high ground to complain about people possibly misrepresenting the basilisk after learning about it from a biased secondary source.

Comment author: somnicule 26 November 2014 08:13:00AM 0 points [-]

Typical low-moderation problems. Repeated discussions of contentious but played-out issues like religion, IQ, status of various fields, etc. The basilisk is an infohazard in that sense at this point, IMO. It's fun to argue about, to the point of displacing other worthwhile discussion.

Comment author: V_V 26 November 2014 10:30:47AM *  2 points [-]

LessWrong also has low moderation. Why would the basilisk generate more trivial discussion than other topics?

Comment author: Rukifellth 25 November 2014 02:09:31AM 0 points [-]

Do you know of it?

Comment author: V_V 25 November 2014 02:01:09PM 1 point [-]

No, I've just found out that it is a board on 4chan.

Comment author: Lumifer 24 November 2014 07:06:42PM 2 points [-]

The market does indeed find the market-clearing price, that's what markets do, but I don't see how that leads to "everything gets sold", especially given that that the market-clearing price changes over time.

Comment author: V_V 24 November 2014 07:26:30PM 0 points [-]

If the supply and demands are perfectly balanced, how is it possible that there are some goods not being sold?

View more: Next