The Decision Problem
In 1928, the mathematician David Hilbert posed a challenge he called the Entscheidungsproblem (which translates to “decision problem”).
Roughly speaking, the problem asks whether there exists an effective procedure (what we would today call an “algorithm”) that can take as input a set of axioms and a mathematical statement, and then decide whether or not the statement can be proved using those axioms and standard logic rules.
Hilbert thought such a procedure probably existed.
Eight years later, in 1936, a twenty-four year old doctoral student named Alan Turing proved Hilbert wrong with a monumental (and surprisingly readable) paper titled, On Computable Numbers, with an Application to the Entscheidungsproblem.
In this paper, Turing proved that there exists problems that cannot be solved systematically (i.e., with an algorithm). He then argued that if you could solve Hilbert’s decision problem, you could use this powerful proof machine to solve one of these unsolvable problems: a contradiction!
Though Turing was working before computers, his framework and results formed the foundation of theoretical computer science (my field), as they can be used to explore what can and cannot be solved by computers.
Over time, theoreticians enumerated many problems that cannot be solved using a fixed series of steps. These came to be known as undecidable problems, while those that can be solved mechanistically were called decidable.
The history of theoretical computer science is interesting in its own right, especially given Hollywood’s recent interest in Turing.
But in this post, I want to argue a less expected connection: Turing’s conception of decidable and undecidable problems turns out to provide a useful metaphor for understanding how to increase your value in the knowledge work economy…
Two Types of Tasks
Let’s begin by briefly turning our attention from Turing to something more mundane: tasks in a knowledge work setting.
The standard definition of a task for a knowledge worker is a clear objective that can be divided into a series of concrete next actions. The productivity guru David Allen, who introduced the “next action” terminology, emphasized in Getting Things Done that if you properly break down your tasks into concrete next actions, your day can function like a factory worker “cranking widgets” as you seamlessly shift from one action to the next.
There are parallels between this definition of a task and Turing’s notion of a decidable problem. In both cases, a clear procedure can be systematically applied to the challenge until it’s solved.
But these decidable tasks are not the only type common in knowledge work.
Another type of task are those that have a clear objective but cannot be divided into a clear series of concrete next actions.
For example:
- A theoretician trying to solve a proof.
- An creative director trying to come up with a new ad campaign.
- A novelist trying to write an award-winning book.
- A CEO trying to turn around falling revenues.
- An entrepreneur trying to come up with a new business idea.
All these examples defy systematic deconstruction into a series of concrete next actions. There’s no clear procedure for consistently accomplishing these goals. They don’t reduce, in other words, to widget cranking.
There are parallels between these types of tasks and Turing’s notion of undecidability. As with Turing’s undecidable problems, any given instance an undecidable task might be solvable, there’s just no systematic approach that’s guaranteed to always work.
On The Value of Undecidability
I argue that the ability to consistently complete undecidable tasks is increasingly valuable in our information economy.
Because these solutions cannot be systematized, this skill cannot be automated or easily outsourced.
Similarly, if you can complete undecidable tasks, you cannot be replaced by a 22-year old willing to work twice your hours at half your pay — as it’s not simply raw effort that matters.
(By contrast, if your day is composed entirely of decidable tasks you’re vulnerable to any of these above dangers.)
That’s the good news.
The bad news is that undecidable tasks are often really hard to complete. Because there’s no easy way to divide them into concrete actions you have to instead throw brain power, experience, creative intuition, and persistence at them, and then hope a solution emerges from some indescribable cognitive alchemy.
You may have guessed where I’m heading with this analysis.
What type of effort supports such difficult cognitive challenges? Deep work.
In other words, understanding the decidable/undecidable task split provides yet another argument for the value of deep work — as it’s only in the cultivation and consistent application of serious concentration that you can expect to succeed where Turing’s machines fail.
Cal,
This is an amazing post. Thanks.
While I’m out of my element in Computer Science and algorithms, I have background and experience in leadership and theology/spirituality. In both areas I’ve seen immense damage done by “leaders” turning “undecidable problems” into rules or a series of steps to be applied in all situations.
Certainly principles, patterns, disciplines, and routines exist to support healthy leadership and/or healthy spirituality. If you don’t learn these and learn them well you will have problems. But we work with people and a changing context. This requires an expansive set of tools and the ability to apply wisdom in context.
This is fantastic Cal. I always like these kind of parallels, this is a brilliant Post. There is yet another “bad thing” working on Undecidable Problems. There may not be a solution at all too for the problem being attempted, Deep Work might give you pleasure, but “does not guarantee a proof for theoretician or award for a writer or revenue for a CEO etc.”. These results/outcomes are dependent on many more factors.
Cal you are going to laugh at this…
Last week the Rhodes Scholars of 2014 were announced. I have read your post about how to become a Rhodes Scholar and I think much of your advice on this topic may have become “outdated”. In your old post you talk about the importance of focusing on a single thing and becoming so good they can’t ignore you. Now read a bio from a Yale student that won the 2014 Rhodes and try not to laugh.
Gabriel M. Zucker ’12 who graduated summa cum laude, majored in ethics, politics and economics, as well as in music. He won many major awards for character and service as well as scholarship. After Yale, he worked at the Abdul Latif Jameel Poverty “Action Lab,” conducting fieldwork in Pakistan and Indonesia. For the past year, he has been associate director of the Connecticut Heroes Project, a campaign to end veteran homelessness in Connecticut. As an undergraduate, Zucker had run Yale’s Hunger and Homelessness Action Project. He is a professional pianist, bandleader, singer-songwriter, and producer. A work he composed for symphony orchestra and big band premiered at Carnegie Hall in 2012. Before pursuing a Ph.D. in economics, Zucker plans to earn a M.Sc. in evidence-based social intervention and policy at Oxford.
Not necessarily contradicting advice. Gabriel Zucker seems to have 2 interests – politics/economics & music, and worked in becoming good in both. I think it seems random when you first read his bio, but all of his activities advance his skills in his two main interests.
Lots of people have have 2 skills/interests that they focus on, including myself (not at the same time tho).
Abdul Latif Jamil is famous economist from Bangladesh btw
Outliers and exceptions always exist. We cant have sweeping generalizations, all theories work under certain conditions 🙂 .
Nameless’s reply above is right on the money.
My analysis of Rhodes Scholars (c.f., this post) promotes the idea that if you focus on a small number of things over a long period of time this focus will generate many related successes, all of which feed off the same concentrated effort.
When you then list out all these related successes in a laundry list, it’s easy to imagine them as each individual accomplishments tackled from scratch, but the reality is that it’s the Rhodes Scholars’s intense focus that enables such a sense of breadth.
Even the ultimate “polymath”, Leonardo Da Vinci, seemed to have a core expertise, which was an eye for detail of physical structure. This served him well in the fields of anatomy, sculpture, architecture, cartography, painting and even with his sketches of possible inventions. An appreciation of what makes a smile enigmatic and an understanding of the structure of a mechanical device are not necessarily disrelated capabilities.
Amazing post, Cal. As a CS PhD student myself, who absolutely loved SGTCIY, I know exactly what you mean by “undecidable problems”.
I’ve sometimes struggling with David Allen’s planning model and often the “next action” is not clear, especially for the truly challenging projects. While GTD has helped me immensely in some ways, it’s very valuable to realize where its limitations lie and where the “undecidable” problems can come in. Recognizing that they *are* potentially undecidable (even if there’s no way to really prove that they are) is a huge step forward. Thanks for making this awesome distinction.
Cal, great article and comparisons with undecidable tasks.
How would you suggest reconciling with projects that require both decidable and undecidable tasks? Coming from software engineering, it’s very common to have a general layout similar to GTD process. However, occasionally a bug or problem will come up that requires large amounts of deep work and throwing away structural procedures to solve a difficult problem.
It’s the messiness between these two extremes that always has me bouncing back and forth between structured and unstructured work.
I’d love to hear your thoughts on trying to balance both of these types of tasks, and what has worked best for you.
Thanks
“It’s the messiness between these two extremes that always has me bouncing back and forth between structured and unstructured work. ” Exactly. As a researcher (and someone with a light background on software engineering) this is one of my biggest problems. Specifically the mental transaction cost of switching between lots of little GTD tasks and deep work tasks. Ideally you schedule out separate times for each, but project work does not always facilitate that type of scheduling.
Please write a blog post on why deep work is valuable here. You just jump to the conclusion without presenting any argument. I don’t see how humans (neural networks) are different from general algorithsm, because we can be modelled by one. In that sense, the only merit of deep work that I see is that you work on the problem. A computer can be put on indefinitely and do deep work as well (brute forcing it, or something more clever).
A little related: there’s a paper about physics professors consistently not solving an introductory textbook physics problem. The authors concluded the professors didn’t have the needed practice in the counter-intuitiveness of the problem. The link is here: https://www.physics.utoronto.ca/~colloq/2013_2014/131010_ChandralekhaSingh.pdf
IMO this could mean that when you do deep work and get an intuition about a field, it may still be very wrong on similar problems that you’re working on. And then I wonder to what extent ‘getting an intuition about a field’ is useful. To what extent will it help you to solve a similar problem faster compared to one who knows the formalities, but only has common sense. The hard thing with undecidable problems is that it’s really hard to understand to what extent your previous experiences are useful problems.
Kahneman has written a literature review about it (and a book).
The undecidable problem parallel that Cal is using seems to be a bit of a stretch although I can see his point. Researchers don’t know how the brain works so stating that it’s a neural network does not characterize the brain.
Your solution of brute forcing things with a computer today is at best impractical. Computers are pretty good at SAT-solving with modern tools and the key to that is propagating information so that the search space can be vastly reduced. There are inherently hard problems in SAT-solving (if you don’t believe P = NP) where the search space can’t be reduced, but those hard problems can be avoided for many usage scenarios.
Research often involves solving a different problem than the problem you initially started with to achieve the same goal. When do researchers take a step back and reconsider the problem? Well, that depends on the problem..
Computers are not good at dealing with these kind of partial and/or fuzzy specifications. Asking a computer to solve a problem with the additional “oh, and hey, if you solve something else that’s interesting or end up somewhere else that might be useful you can stop and report back to me” does not work.
—Turning undecidable tasks into decidable tasks—-
The way I think about undecidable tasks is to use a block of time spent instead of the end result. E.g.
(1) “Spend 5 blocks of 25 minutes on Proof”
vs
(2) “Find proof of Theorem X”
Instead of dealing with the undecidable task in (2), we can deal with the decidable task in (1).
See Cal’s Article on Fixed Schedule Productivity:
https://calnewport.com/blog/2008/02/15/fixed-schedule-productivity-how-i-accomplish-a-large-amount-of-work-in-a-small-number-of-work-hours/
Cal-
Great post. Regarding your research. Have you looked into Steve Perlman (Artemis Networks)?
Hi,
Sorry this is kind of random, but what is the notebook you use daily to create your plans? On the right all I see is the captioning, not an image or link so could you please provide that to me? Thanks so much.
Turn off your ad blocker.
Cal,
A thought-provoking piece, thanks.
Could ‘Decidable’ problems also reasonably be considered ‘rational’ problems?
Using the examples you provided as a starting point, my gut tells me that ‘undecidable’ problems, at least day to day ones, are predominantly dictated by the irrational component of human behaviour.
For example:
A creative director trying to come up with a new ad campaign. – Will consumers ‘like’ the campaign? An ‘irrational’ behaviour
A novelist trying to write an award-winning book. – Will readers ‘like’ the book enough for it to win awards? An ‘irrational’ behaviour
A CEO trying to turn around falling revenues. – Will consumers ‘like’ the product enough to buy more. An ‘irrational’ behaviour
An entrepreneur trying to come up with a new business idea. – Will potential customers ‘like’ the business? An ‘irrational’ behaviour
A theoretician trying to solve a proof. – In this case the theoretician *is* the irrational being and so is trying to minimize the irrationality in order to rationally and logically ‘solve’ the proof.
What do you think?
Irving Good distinguished between what he called Type 1 and Type 2 rationality.
In this context, Type 1 rationality would solve the problem (if it can be solved, otherwise endlessly look for a solution), and Type 2 rationality would incorporate a measure of your belief that the problem is decidable or not (i.e., after spending some effort on the problem or gaining some insight, you may have very little confidence that the problem is decidable, and switch to working on something else).
I think what you’re talking about falls into the Type 2 category. Whether customers will “like” the outcome you’re trying to produce in the first four examples isn’t irrationality, it’s the director/novelist/CEO/entrepreneur incorporating their uncertainty about the customers’ preferences into their decision of whether to take on these problems.
Good explicitly discussed your last example of the theoretician. Before either proving or disproving a proposition, the theoretician is uncertain of whether it is true or false. After working on the proof for some time without any success, the theoretician decides whether to continue on this problem, and must weigh the costs and benefits of continuing with the likelihood of success.
Such an ah-ha moment here. At the root of many procrastination and productivity problems is the decision problem. If you are a knowledge worker faced with much undecidability and you’re anxiously wanting to get things done, the next action is usually going to be a decidable task rather than the one that requires deep work…which leads to procrastinating on deep work and less productivity in the areas that could make you so good they can’t ignore you. 🙁
Well said Linda. That is the problem I faced and I do not have any concrete solution. Setting priority by means of daily and weekly plan, as Cal mentioned in his previous posts, may work.
Thomas Edison is quoted as saying, “Genius is one percent inspiration, ninety-nine percent perspiration.”
On the surface of it, perspiration sounds more like cranking widgets than deep work. If one percent is the part that only deep work addresses, and 99-percent is widget-cranking, then task-accomplishing throughput could be critical.
Is he wrong? Maybe his advice applies to a different time, or a different field of endeavor, where widget-cranking is more important than the deep work.
On the other hand, perhaps by perspiration he means a tireless pursuit required to develop an initial inspiration to it’s greatest possible expression.
What is your take on how the quote applies in the context of this article?
I think that the idea sparked some good discussion. Some of the discussion has strayed to using the terms “decideable” and “undecideable” in an informal way – as analogs for the types of work we can efficiently complete using a system like GTD, and the types of work that might require deep work.
Is there a chance that it is possible to systematize what you call deep work, even if we have not been able to do so thus far?
Next action, breathe
Nice article and great research!
– I recently started a blog to help people study more efficiently. My first article is on memorization. Come check it out!
https://studyingright.blogspot.com/?m=1
Cal, I find your student advice and posts are valid for people studying and working in the US/UK. I studied in Europe for my school and came to India for my undergraduate studies. I used to unconsciously apply your advice in school and it was very, very helpful. However since coming here, I find that none of the advice is applicable. In the college I am studying, there is no option to ‘drop courses’ in my field. Every single person mandatorily does the exact same set of subjects every semester. As a school student, I would always try to understand the topics in physics and mathematics intuitively rather than solve problems, I rarely “studied” and still got 95-100% in everything. Here if I have a doubt and ask my classmates or professors why there is certain step in a certain answer to a problem, the reply is “to get to the answer” and “just memorise how to do it” for the exam. These are the students that are the ones that score the most marks.
In an economics course I was doing, when I got my grades to an internal exam, I was shocked seeing that I barely got 45%, as I knew the topics very well. My friend got 65% (no one gets above 75% in any subject, even if all your answers are correct). Since we got the exam paper back, my friend gave me her paper so I could understand how the professor was grading. It turns out that quantity of writing matters more than quality of writing (putting it very mildly). My friends told me “forget writing well, just write a lot of pages and bullshit” and that the professors do not actually care what you write, they flip the papers, see a lot of words and give the marks based on that. For the next semester, I focused on quantity of writing in exam, and I would say the out of 15 pages I wrote for each exam, maybe 2 of them had any decent content. My grades jumped up dramatically.
Additionally, here extracurriculars are of little value, and to enter into a top college or postgraduate program, only your grades and test scores matter.
Cal, would you have any advice regarding this system of education? Granted that the Indian education system is far from perfect, but currently I do need to do well here in order to get into Master’s programme of my choice. I am finding it difficult shifting from a deep thinking system to a system where just the quantity of words written on your exam determine your grades and your future.
Is there a way to incorporate deep work and thinking here without wrecking my grades?
This isn’t directly related to this post, but I’m curious how you balance the (implicit and often even explicit) expectation to work long hours with your method of working. As a junior faculty member at a research university, I worry that admitting that I don’t work 60 hours a week will lower my colleagues’ (aka tenure case voters’) perceptions of my work, even though I’m on track for tenure. Do you just accept the fact that you’re going against the grain? Or do you find that it isn’t an issue?
I don’t think anyone cares about the details of my work habits. They do care very much about my CV.
I think another term for undecidable tasks is creativity. We have been hearing for several years now about the future importance of being creative in one’s work. I think the concept is starting to be more widely understood as more speakers (eg Ken Robinson as well as Jeremy Howard’s TED talks) help us to make sense of the mind boggling rate of change that we all must deal with. Frey and Osborne’s paper (no relation) “THE FUTURE OF EMPLOYMENT: HOW SUSCEPTIBLE ARE JOBS TO COMPUTERISATION?” is well done and adds two more work characteristics to undecidable tasks (creativity), namely, high level social skills & physical dexterity to the list of future jobs that will not easily be lost to computerisation. I believe this is important information especially for those like myself who are looking at new business ventures.
Unrelated to the core content, but I think Kurt Godel was the first to shoot down the Entscheidungsproblem. The paper you posted says it is from 1936, Kurt Godel published in 1931.
Brilliant article along with the follow-up, “Deep Habits…”
Just wanted to mention that in the second paragraph, I think the use of the spelling of “there” instead of “their” is what was intended. Very small error in what is a genius proposition and solution.