This is a special post for quick takes by Thomas Kwa. Only they can create top-level comments. Comments here also appear on the Quick Takes page and All Posts page.
A toy model of intelligence implies that there's an intelligence threshold above which minds don't get stuck when they try to solve arbitrarily long/difficult problems, and below which they do get stuck. I might not write this up otherwise due to limited relevance, so here it is as a shortform, without the proofs, limitations, and discussion.
The model
A task of difficulty n is composed of n independent and serial subtasks. For each subtask, a mind of cognitive power Q knows Q different “approaches” to choose from. The time taken by each approach is at least 1 but drawn from a power law, P(X>x)=x−α for x>1, and the mind always chooses the fastest approach it knows. So the time taken on a subtask is the minimum of Q samples from the power law, and the overall time for a task is the total for the n subtasks.
Main question: For a mind of strength Q,
what is the average rate at which it completes tasks of difficulty n?
will it be infeasible for it to complete sufficiently large tasks?
Results
There is a critical threshold Qcrit of intelligence below which the distribution of time to complete a subtask has infinite mean. This threshold depends on α.
This implies that for an n-step task, the median of average time-per-subtask grows without bound as n increases. So (for minds below the critical threshold) the median time to complete a whole task grows superlinearly with n.
Above the critical threshold, minds can solve any task in expected linear time.
Some distance above the critical threshold, minds are running fairly close to the optimal speed, and further increases in Q cause small efficiency gains.
I think this doesn't depend on the function being a power law; it would be true for many different heavy-tailed distributions, but the math wouldn't be as nice.