10
$\begingroup$

An undecidable problem is a decision problem proven to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. I wonder if there are examples of probabilistic approaches (in the following sense below) that solve such problems.

By a probabilistic approach, I mean a nondetermistic algorithm such that for each input it outputs in finite time and the answer is correct with probability strictly larger than $50\%$. In other words, it is similar to PP but I do not require polynomial time (shall I call it "FiniteP", or it has a name already in complexity theory?). Please do not confuse this with a nondetermistic algorithm that performs probabilistically, but still tries to find a definite answer before halting.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Possibly related: MIRI's paper on Logical induction, which tries to probabilistically predict the provability of statements from patterns in easily-proved lemmas. $\endgroup$
    – Jacob Manaker
    Oct 11, 2022 at 16:48
  • 2
    $\begingroup$ I'm positive the answer to this question in the most general case is "no" - I defer to the smart people on this stack to describe why. However I think you might consider a frame challenge - maybe you only care about a subset of problems, and maybe that subset has patterns that heuristically suggest a decision that is correct more than half the time. Consider timsort - it's a hybrid sorting algorithm that performs remarkably well because it exploits order that already exists in the elements it is sorting. Against random data it's nothing special, but lots of real world data is not random. $\endgroup$
    – Blackhawk
    Oct 11, 2022 at 18:39

4 Answers 4

Reset to default
19
$\begingroup$

So, we have a TM $M$ that can in addition flip a fair coin. We have the promise that for every input $M$ will eventually halt and give an answer, no matter what the coin results are. Moreover, we demand that the probability of getting the correct answer is greater than 0.5.

First let us observe that because $2^\omega$ is compact, we can move from "For every sequence of coin tosses there is a finite time $t$ where $M$ halts" to "There is a finite time $t$ such that $M$ halts by time $t$ regardless of the coin outcome". This in turn means that for each input to $M$, there are only finitely many (no more than $2^t$) many computation pathes that are possible.

A deterministic machine $N$ can simulate what $M$ would do for each of the finitely many coin results. As more than half of these return the correct answer, a simple majority vote suffices for $N$ to figure it out.

So your class FiniteP consists of exactly the decidable problems.

Improve this answer
$\endgroup$
13
  • 4
    $\begingroup$ Can you please elaborate on the first sentence of the second paragraph? I understand the conclusion, but I don't understand the transition. $\endgroup$
    – Dmitry
    Oct 10, 2022 at 22:36
  • 3
    $\begingroup$ @Student: "I don't want the machine to just guess by flipping a fair coin": Of course not. But a probabilistic approach requires a source of randomness, and Arno's answer uses a sequence of coin flips (that is: a sequence of random bits) as that source. $\endgroup$
    – ruakh
    Oct 11, 2022 at 4:36
  • 5
    $\begingroup$ Does this still work if we replace "always halts" with "halts with probability 1"? For example a program which keeps flipping a coin until it gets heads is not guaranteed to halt (it could keep flipping tails) but in practice it does halt because the probability of not halting is 0. I guess the compactness argument doesn't work in this case but maybe there is some other trick? $\endgroup$
    – Marc
    Oct 11, 2022 at 8:28
  • 4
    $\begingroup$ @Marc Indeed, the argument needs to be changed, but the conclusion stands. What we need to do there is to use dove-tailing to explore all potential random sequences; and keep track of those finite bit strings than lead to halting with a particular answer. At some point, we will have seen more than 0.5 probability mass accumulated by one answer, and that one we can trust. $\endgroup$
    – Arno
    Oct 11, 2022 at 9:57
  • 2
    $\begingroup$ I think the lemma "we can move from [...] to [...]" needs a paragraph and a proof of its own $\endgroup$
    – Agnishom Chattopadhyay
    Oct 11, 2022 at 20:25
2
$\begingroup$

What do you mean by randomness on nondeterministic TM? I think such a NTM with correct probability $\geq 2/3$ should be in PH by Sipser-Lautemann, and with probability 50% it's like something related with #P and NP (maybe $\sf \#P^{NP}$?). I guess it cannot solve undecidable problems since nondeterminism and randomness are both some weakened version of counting, which is still "in the control of decidability". (i.e., you can use some DTM to simulate their behavior, though the time complexity maybe super huge like super-super-exponential. But it's still a DTM with finite amount of time anyway. It's a valid decider.)

Improve this answer
$\endgroup$
2
$\begingroup$

Yes, and it includes the Halting Problem, but it's not very useful.

The solution to the Halting problem is known in the particular case of the program that ends immediately. Actually there are arbitrarily many programs that are known to halt; for example all programs with no looping instructions.

So suppose we write the following program: "If the input program obviously halts according to one or more quick tests, return True. If not, return a coin flip." The coin flip gets 50% of the non trivial cases (which are the vast majority), and the reasoned test gets 100% of of the trivial cases. By simple arithmetic, the routine as a whole will "solve" the halting problem strictly more successfully than 50%. Such a construction works for any problem for which there are any decidable special cases.

The reason that this is not very useful is that the randomness doesn't actually add any information, and so it doesn't stack informatively. When we talk about probabilistic algorithms we either expect that independent runs of the routine give independent answers which are each more reliable than not. The notion is that if you have a mere 51% successful independent random guesser run ten thousand times, the majority guess will be right with 97% probability. However, if you have a 51% successful random guesser that just sticks to its first guess, after 10,000 attempts you're still at 51%! Independence is critical. In particular, you need independence in your >50% chance of success. In this construction, only bit that gets better than mere guessing is deterministic and reproducible, while the random bit is completely disconnected from reality. That means that although we can get something to a 50%+ε for all problems with some decidable special cases, we can't leverage that fact to get arbitrarily high.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I recognise that this may feel like a bit of a bait and switch, but I think it's illuminating to work through what features of probabilistic algorithms are useful. $\endgroup$
    – Josiah
    Oct 11, 2022 at 22:13
  • 5
    $\begingroup$ "By simple arithmetic, the routine as a whole will "solve" the halting problem strictly more successfully than 50%" - This reasoning fails when there are infinitely-many possible programs. An infinite subset of programs could still have measure 0. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Oct 11, 2022 at 22:30
  • $\begingroup$ @BlueRaja-DannyPflughoeft has a point, but I still suspect your answer is correct for some undecidable problems, so it gets a tentative upvote from me. $\endgroup$
    – wizzwizz4
    Oct 11, 2022 at 23:05
  • 5
    $\begingroup$ This answer is wrong. In the question, the probability is taken only over the randomness (the coin flips) of the probabilistic algorithm. This answer seems to be focusing on the probability taken over a random choice of input programs, which is a different situation that's not what the question is asking about. It's much harder to build an algorithm that, for every input program $P$, correctly answers whether $P$ halts with probability $>0.5$ (here the probability is taken over the random choices of the algorithm but not over the choice of $P$, as $P$ is not chosen randomly). $\endgroup$
    – D.W. ♦
    Oct 11, 2022 at 23:53
  • 1
    $\begingroup$ I don't understand your analogy. Given any fixed string of finite length as code, either it halts or not, right? The heuristic code g() seems to be what you are referring to, but the point is that such g() doesn't exist - it cannot be written down with a well-defined halts(). $\endgroup$
    – Student
    Oct 12, 2022 at 12:25
-2
$\begingroup$

There are a few different probabilistic methods that can be used to try and solve undecidable problems. One such method is called Markov chains, which are a type of stochastic process. Essentially, a Markov chain is a mathematical model that describes the evolution of some system over time, using probabilities to calculate the most likely next state for the system.

Another probabilistic method that can be used to solve undecidable problems is Bayesian inference. Bayesian inference is a technique for updating beliefs in the light of new information. It allows us to combine our existing knowledge with new information in order to make better decisions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are there any specific examples that have been implemented? $\endgroup$
    – Student
    Oct 17, 2022 at 16:33
  • $\begingroup$ I suspect this answer is based on a misunderstanding of some sort. Markov chains don't solve undecidable problems. That's not what they're designed for, nor is it what they do. Similar comments apply to Bayesian inference. $\endgroup$
    – D.W. ♦
    Oct 17, 2022 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.