1

I'm trying to clarify my understanding of decidability of a language. The following question is totally made up by me so I hope it makes sense.

Let $L = \{A: A \text{ is an algorithm that can prove "There are an infinite number of primes"}\}$

In light of the comments, what if I reformulate the question as: Let $L = \{T: T \text{ is a theorem that has been proven true}\}$

For example, "There are an infinite number of primes" is such a theorem. Since Euclid proved that there are an infinite number of primes, does that mean L is decidable? If not, it must mean that Euclid's proof is not an algorithm. In that case, I'd like to understand why Euclid's proof is not an algorithm.

user137481
  • 2,605
  • 3
    In this context, Euclid's proof would (or would not) be a single element of $L$; this would have no bearing on whether or not $L$ is decidable. Whether it is or is not an element of $L$ depends on whether you can encode Euclid's proof as an "algorithm". – vadim123 Mar 23 '14 at 22:02
  • @vadim123 You're right. I was having some difficulty trying to frame the question in the proper context. fgp and mlo105 interpreted my question in the intended context which I was unfortunately unable to convey since I'm new to the topic. – user137481 Mar 23 '14 at 23:31
  • @undergrad Please don't modify question so radically as you have done here - it potentially invalidates existing answers and comments. Instead of replacing your definition of $L$, you should have ammended the question, e.g. by adding "In the light of the comments, what about the generalisation $L = \ldots$". – fgp Mar 24 '14 at 10:30
  • @undergrad Btw, your set is trivially decidable now, at least of you assume that the amount of knowledge humans have acquired is finite. Because then, only finitly many theorems have so far been proven to be true, so checking whether some theorem is in $L$ just requiring comparing $T$ to a finite list. BTW, you're still confused, I think, about what being decidable means for a set. It doens't means that it's elements are decidable, it just means that whether or not a particular element is in the set is decidable... – fgp Mar 24 '14 at 10:33
  • @fgp, I think I've got it now. Let's start with L = {i: i is prime}. The set of primes is infinite. However, since there are methods to decide if i is prime or not, L is decidable. Now, let L = {n: The Collatz conjecture is true for the natural number n}. In this case, L would be undecidable since if the conjecture was false for a given n, the "algorithm" would never halt. Now, let L = {n: The Collatz conjecture is true for less than n natural numbers}. Again, L is undecidable. While, the conjecture has been proven for many numbers, all it means is that we've not found any counterexamples yet. – user137481 Mar 24 '14 at 19:05
  • @undergrad Nearly, but not quite. The set $L$ containing $n$ if the collatz conjecture is true for $n$ might be undecidable. Undecidable means that you can prove that there's no algorithmn which decides whether $n$ is in the set or not. In this case, we don't know that - we just know that you algorithm has been found. Same goes for the last set - if the collatz conjecture were to be settled positively, we'd know that the last set is empty. Today, we don't - but that doesn't mean it's undecidable, just that it hasn't been decided yet. – fgp Mar 24 '14 at 19:25
  • @fgp Formally, $L \subset \mathbb{N}$ being undecidable means that there is no recursive function $f$ such that $f(n) = 1$ exactly if $n \in L$. In other words, that the characteristic function $f$ of $L$ is not recursive. – fgp Mar 24 '14 at 19:28
  • @fgp The definition of decidability requires that there be a method that accepts a string that is in L, rejects a string that is not and in either case must halt. If the Collatz conjecture is false for some n, then the algorithm would never halt. My understanding was this may mean L is recognizable but it is not decidable. It looks like I'm still missing some points of the definition. – user137481 Mar 24 '14 at 21:21
  • @undergrad That depends on the algorithm! Sure, if you just naive compute the collatz sequence until you reach $1$, then testing the conjecture for $n$ doesn't terminate unless it holds. But maybe there is some algorithm that tells in finite time whether the conjecture holds for a particular $n$. The point is, we don't know. Undecidable, OTOH, says much more - it says that there cannot possibly be an algorithm which decides wheter a particular $n$ is in the set. Not just that none is known, but that none can exist. – fgp Mar 24 '14 at 23:25
  • @fgp apologies for the late response. Was finishing up term assignments. I think I get your point now. It isn't sufficient that there be no known algorithm. We must be able to prove that no such algorithm can possibly exist. Generally, we show that the existence of such an algorithm would lead to a contradiction. Or we try to show that the problem is just the Halting problem in disguise. – user137481 Mar 31 '14 at 19:14
  • @undergrad Exactly. Quite often the latter... – fgp Mar 31 '14 at 19:19
  • @fgp, thanks! That was instructive. – user137481 Mar 31 '14 at 19:24

2 Answers2

2

As it stands, your question is hard to answer properly, because you don't formalize what kind of "algorithm" you have in mind, and how it proves "There's an infinite number of primes".

But there's a very general theorem in recursion theory, which basically says that any set of recursive functions (i.e. algorithms) which is defined in terms of the behaviour of it's member functions, rather than some syntactic property, is undecidable.

The reason is, roughtly, that you can always take an algorithm - even a trivial one that is easly shown to always terminate - and modify it so that before it terminates and returns its result, it attempts to solve some undecidable problem like a particular instance of the halting problem.

Thus, for all usual formalizations of "algorithm" and "proof", the answer to your question is no, $L$ is undecidable.

fgp
  • 21,050
  • My "naive" algorithm for determining truth/falsity of "there are an infinite number of primes" would be to simply test every number. If the set was infinite, my algorithm would never halt. But even if the set was finite, how would we know without testing all numbers? But then testing all numbers also means it would never halt. But Euclid's proof certainly "halts". If Euclid's proof is a "method" or "algorithm" then by definition L would be either decidable/recognizable. From the answers, I'm getting the impression that Euclid's proof is not an "algorithm". I'd like to understand why. – user137481 Mar 23 '14 at 23:42
  • @undergrad Informally, an algorithm is something that computes a result by carrying out a series of computations. There are varies ways to formalize that - the most common being Turing Machines, Recursive Functions and Lambda Calculus, and they're all equivalent. Your "naive" algorithms can be formalized in all of them, and will disprove the theorem in finite time if it is wrong, but won't be able to prove it. – fgp Mar 24 '14 at 09:59
0

A language is decidable if there exists a Turing Machine that halts on all inputs and accepts on strings in the language. So your language is undecidable, as this is exactly the halting problem. If we have an algorithm, it will always halt, so a Turing Machine can accept it. However, a heuristic may not halt. So $L$ is recursively enumerable, but not decidable.

Now in terms of Euclid's proof, I would say this is not an algorithm. Given any finite set of primes (ie., suppose we have a finite set of all the primes), an "algorithm" for Euclid's lemma will reject the set, inferring an additional prime. So what will it accept? There are infinite number of primes, but Turing Machines are restricted to finite input strings. So it's not computationally feasible to really deal with the set of all primes.

ml0105
  • 14,674