Set of all decision problems solvable by a Turing machine, i.e. that decide if a string belongs to a recursive language.
Or in other words: there is no Turing machine that always halts for every input with the yes/no output.
Every undecidable problem must obviously have an infinite number of "possibilities of stuff you can try": if there is only a finite number, then you can brute-force it.
Lists of undecidable problems.
Coolest ones besides the obvious boring halting problem:
One of the most simple to state undecidable problems.
A:
- decidable problem is to a decision problem
- like a computable problem is to a function problem
Ciro Santilli participated in a double degree program, so he obtained have engineering degrees in both:
- 2010 - 2014: École PolytechniqueMaster 2 degree in applied mathematics.
- Ciro Santilli's undergrad studies at the University of São Paulo
Despite studying in great institutions with great teachers, Ciro feels that:
- most of what he knows came from the Internet, man pages, books and his parents
- actual projects matter much more than those pieces of paper called Diplomas. You should not do like Ciro who basically did nothing but school mandated work, but instead grow some balls and focus much more or entirely on your projects
This motivated Ciro to work on OurBigBook.com.
Difference between recursive language and recursively enumerable language by 
Ciro Santilli 40 Updated 2025-07-16
Ciro Santilli 40 Updated 2025-07-16This is the true key question: what are the most important algorithms that would be accelerated by quantum computing?
Some candidates:
- Shor's algorithm: this one will actually make humanity worse off, as we will be forced into post-quantum cryptography that will likely be less efficient than existing classical cryptography to implement
- quantum algorithm for linear systems of equations, and related application of systems of linear equations
- Grover's algorithm: speedup not exponential. Still useful for anything?
- Quantum Fourier transform: TODO is the speedup exponential or not?
- Deutsch: solves an useless problem
- NISQ algorithms
Maybe there is some room for doubt because some applications might be way better in some implementations, but we should at least have a good general idea.
However, clear information on this really hard to come by, not sure why.
Whenever asked e.g. at: physics.stackexchange.com/questions/3390/can-anybody-provide-a-simple-example-of-a-quantum-computer-algorithm/3407 on Physics Stack Exchange people say the infinite mantra:
Lists:
- Quantum Algorithm Zoo: the leading list as of 2020
- quantum computing computational chemistry algorithms is the area that Ciro and many people are te most excited about is
- cstheory.stackexchange.com/questions/3888/np-intermediate-problems-with-efficient-quantum-solutions
- mathoverflow.net/questions/33597/are-there-any-known-quantum-algorithms-that-clearly-fall-outside-a-few-narrow-cla
Computational problem where the solution is either yes or no.
When there are more than two possible answers, it is called a function problem.
Decision problems come up often in computer science because many important problems are often stated in terms of "decide if a given string belongs to given formal language".
The canonical undecidable problem.
Of course, because what we know about the halting problem, there cannot exist a single decider that decides all Turing machines.
E.g. The Busy Beaver Challenge has a set of deciders clearly published, which decide a large part of BB(5). Their proposed deciders are listed at: discuss.bbchallenge.org/c/deciders/5 and actually applied ones at: bbchallenge.org.
But there are deciders that can decide large classes of turing machines.
Many (all/most?) deciders are based on simulation of machines with arbitrary cutoff hyperparameters, e.g. the cutoff space/time of a Turing machine cycler decider.
The simplest and most obvious example is the Turing machine cycler decider
Bibliography: discuss.bbchallenge.org/t/decider-cyclers/33
Example: bbchallenge.org/279081.
These are very simple, they just check for exact state repetitions, which obviously imply that they will run forever.
Unfortunately, cyclers may need to run through an initial setup phase before reaching the initial cycle point, which is not very elegant.
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 3. Visual Studio Code extension installation.
Figure 4. Visual Studio Code extension tree navigation.
Figure 5. Web editor. You can also edit articles on the Web editor without installing anything locally.Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.Video 4. OurBigBook Visual Studio Code extension editing and navigation demo. Source. 
- Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact