First, God says, "Yeah, but I'm not going to tell you," not "Yeah, but you can't do it." I think there is an implication that it *is* possible for the human, but the human doesn't know how (and presumably never will).
Second, if we allow God some form of hypercomputation, we can still potentially tweak the original argument by asking not about those subsets of natural numbers that can be produced by an algorithm, but by those that can be produced by such a hypercomputer. And then there is a corresponding argument via the halting problem for that hypercomputer that still goes through.
Of course, if God can skip the entire hierarchy of Turing degrees by just looking through the entire set of natural numbers and counting whether it has infinitely many primes or not, then that is a different matter. But I think it is still fair to call him a deceitful deity if this is the only option!
I don't fully buy the argument here: even though EnumPShifted cannot be decided, there *does* exist a different program that outputs the same set of numbers as EnumPShifted and that *can* be decided. I think you transformed WSG's claim into a stronger claim when you formalized it as being about programs, rather than about the sets of numbers themselves.
Or rather, I think you turned it into a claim that is in some ways stronger and in some ways weaker. The set of numbers in the Busy Beaver sequence is well-defined, but cannot be output by any program. In my interpretation, WSG is claiming that even this set of numbers can be decided. (Which is extremely hard to believe, although I can't think of a way to prove him wrong.)
You are right, of course, that there is a different program that has the same output as EnumPShifted, but for which it is trivial to decide whether it has infinitely many primes. But you cannot determine algorithmically which it is.
I can prove quite definitively that this really is about sets of numbers, and not about programs, however. Let's seemingly restrict ourselves and just consider sets of numbers of the following form: we take an integer polynomial P in some number of variables, and define a corresponding set S that is the set of all natural numbers x such that we can solve P(x,x_2,x_3,...,x_n)=0 in the natural numbers. This is called a Diophantine set.
For example, the collection of natural numbers n^2+1 is Diophantine, corresponding to the polynomial X-Y^2-1. This seems very much in the spirit of what Zach had in mind---if anything, as you say, it feels restrictive.
However, here's the kicker: Diophantine sets and computably enumerable sets are the exact same thing! This was the MRDP theorem proved in 1972, which demonstrated that no algorithm can possibly determine whether a Diophantine set is empty or not. But if you can't determine whether it is empty or not, you won't be able to determine whether it has infinitely many primes in it either.
And, of course, if we can't even work this out for the very, very special case of Diophantine sets, then there is absolutely no hope of doing it for any larger collection (such as one that might include the Busy Beaver sequences).
This reminds me of some thought experiments I had gone through. The priest at my church growing up is a math professor at the University of Utah with a degree in Algebraic Topology. I've wondered if he would have been religious had he gone into number theory or computer science. After all the God that is said to be all knowing and all powerful still could not create a computer program to solve the halting problem. This means that we cannot have a "naive god theory" that states god can do "any action described by words". That means that there are limits on how God can be described.
You're missing an n += 1 line after the a loop in your FLT_search function. As is, the code quite clearly loops forever as the k loop body never gets executed (as range(3,3) = []), so it just does a small trivial loop over and over, and fails to test even a single FLT quadruple.
If God were an algorithm, your answer is, of course, correct.
But if God could do an infinite (or uncountable infinite) number of operations in a finite time, wouldn't your answer change?
Yes, with some caveats!
First, God says, "Yeah, but I'm not going to tell you," not "Yeah, but you can't do it." I think there is an implication that it *is* possible for the human, but the human doesn't know how (and presumably never will).
Second, if we allow God some form of hypercomputation, we can still potentially tweak the original argument by asking not about those subsets of natural numbers that can be produced by an algorithm, but by those that can be produced by such a hypercomputer. And then there is a corresponding argument via the halting problem for that hypercomputer that still goes through.
Of course, if God can skip the entire hierarchy of Turing degrees by just looking through the entire set of natural numbers and counting whether it has infinitely many primes or not, then that is a different matter. But I think it is still fair to call him a deceitful deity if this is the only option!
I don't fully buy the argument here: even though EnumPShifted cannot be decided, there *does* exist a different program that outputs the same set of numbers as EnumPShifted and that *can* be decided. I think you transformed WSG's claim into a stronger claim when you formalized it as being about programs, rather than about the sets of numbers themselves.
Or rather, I think you turned it into a claim that is in some ways stronger and in some ways weaker. The set of numbers in the Busy Beaver sequence is well-defined, but cannot be output by any program. In my interpretation, WSG is claiming that even this set of numbers can be decided. (Which is extremely hard to believe, although I can't think of a way to prove him wrong.)
You are right, of course, that there is a different program that has the same output as EnumPShifted, but for which it is trivial to decide whether it has infinitely many primes. But you cannot determine algorithmically which it is.
I can prove quite definitively that this really is about sets of numbers, and not about programs, however. Let's seemingly restrict ourselves and just consider sets of numbers of the following form: we take an integer polynomial P in some number of variables, and define a corresponding set S that is the set of all natural numbers x such that we can solve P(x,x_2,x_3,...,x_n)=0 in the natural numbers. This is called a Diophantine set.
For example, the collection of natural numbers n^2+1 is Diophantine, corresponding to the polynomial X-Y^2-1. This seems very much in the spirit of what Zach had in mind---if anything, as you say, it feels restrictive.
However, here's the kicker: Diophantine sets and computably enumerable sets are the exact same thing! This was the MRDP theorem proved in 1972, which demonstrated that no algorithm can possibly determine whether a Diophantine set is empty or not. But if you can't determine whether it is empty or not, you won't be able to determine whether it has infinitely many primes in it either.
And, of course, if we can't even work this out for the very, very special case of Diophantine sets, then there is absolutely no hope of doing it for any larger collection (such as one that might include the Busy Beaver sequences).
This reminds me of some thought experiments I had gone through. The priest at my church growing up is a math professor at the University of Utah with a degree in Algebraic Topology. I've wondered if he would have been religious had he gone into number theory or computer science. After all the God that is said to be all knowing and all powerful still could not create a computer program to solve the halting problem. This means that we cannot have a "naive god theory" that states god can do "any action described by words". That means that there are limits on how God can be described.
You're missing an n += 1 line after the a loop in your FLT_search function. As is, the code quite clearly loops forever as the k loop body never gets executed (as range(3,3) = []), so it just does a small trivial loop over and over, and fails to test even a single FLT quadruple.
Indeed! Thank you for catching that; I have fixed it.
Hello Senia, good to meet you here. There is a bug in the Countdown program: $n$ should be decremented each time, not incremented.
Indeed! I have fixed it.
Will you now have time to publish a book with your Quora Answers?
Not for a long time, I am afraid. On the other hand, that is one of the things that this Substack is for.