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.
Nice if it is a general feature of heavy-tailed distributions. Why do we expect tasks to be heavy tailed? It has some intuitive force certainly. Do you know of a formal argument?
The time to complete a task using a certain approach should be heavy-tailed because most approaches don’t work or are extremely impractical compared to the best ones. Suppose you’re trying to write an O(n log n) sorting algorithm. Mergesort is maybe easy to think of, heapsort would require you to invent heaps and take maybe 10x more time, and most ideas out of the space of all possible ideas don’t work at all. So the time for different approaches definitely spans many orders of magnitude.
The speed at which humans can do various cognitive subtasks also differs by orders of magnitude. Grandmasters can play chess >1000 times faster at equal skill level than lesser players, as evidenced by simuls. Filling in a clue in a crossword sometimes takes me 1 second but other times might take me an hour or longer if I didn’t give up first.
The independent-steps model of cognitive power
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.
Nice if it is a general feature of heavy-tailed distributions. Why do we expect tasks to be heavy tailed? It has some intuitive force certainly. Do you know of a formal argument?
The time to complete a task using a certain approach should be heavy-tailed because most approaches don’t work or are extremely impractical compared to the best ones. Suppose you’re trying to write an O(n log n) sorting algorithm. Mergesort is maybe easy to think of, heapsort would require you to invent heaps and take maybe 10x more time, and most ideas out of the space of all possible ideas don’t work at all. So the time for different approaches definitely spans many orders of magnitude.
The speed at which humans can do various cognitive subtasks also differs by orders of magnitude. Grandmasters can play chess >1000 times faster at equal skill level than lesser players, as evidenced by simuls. Filling in a clue in a crossword sometimes takes me 1 second but other times might take me an hour or longer if I didn’t give up first.