4 ms·
Yes, there is a small program, for which you could be one of the most famous mathematicians if you could tell whether it terminates or not: i = 4; while(there
by nadam 13y ago
Yes, there is a small program, for which you could be one of the most famous mathematicians if you could tell whether it terminates or not:
i = 4;
while(there exists such p and q that prime(p) and prime(q) and p+q == i)) i+=2;
keyword: Goldbach conjecture. The Goldbach conjecture states that this program will never halt. No one could prove this yet; seems to be really hard.
- StavrosK 13y agoI find your code hilarious in that, if it ever terminates, it doesn't print the two primes.
- pi18n 13y agoA true mathematician; nadam only cares that a solution exists.
- tomjen3 13y agoThat program doesn't run forever, you didn't declare that there what had to exist for the (just there exist) and prime isn't declared (is prime? highest prime which is a factor in the argument?).
- nadam 13y agoThe Goldbach conjecture is this: "Every even integer greater than 2 can be expressed as the sum of two primes." My program is simply constructed in such a way that it terminates if and only if the Goldbach conjecture is not true. Maybe my pseudocode is not very precise (and also english is not my mother language), but given the Goldbach conjecture anyone can construct the program more precisely if needed.
- lifeformed 13y agoBut if you were to code out such a program it would have to still have an upper bound for the size of the numbers you are testing. My implementation would look like this: int i = 4; bool sumFound = true; while(sumFound) { sumFound = false; for(int p = 0; p < MAX_INT && !sumFound; p++) { if (isPrime(p)) { for (int q = 0; q < MAX_INT && !sumFound; q++) { if (isPrime(q)) { if (p + q == i) { i += 2; sumFound = true; } } } } } } You could use big integers, but it'd still be bound by whatever the max size is for that. This program would eventually terminate. Could you write an implementation where the limitations of the system don't get in the way of the theoretical mathematical limitation? I guess you could build some system which can accommodate arbitrarily large numbers, but even that would be limited by the computer specs. I guess what I'm saying is, isn't the implementation of the program the test in itself?
- nadam 13y agoThe program must run on the Turing machine. The Turing machine has an infinite tape, so it is able to represent arbitraily large numbers on its tape. It is a different question that a real Turing machine cannot be built in the known physical universe which contains only a finite number of atoms.
- nijk 13y agoSince you don't have a real Turing machine, why would you care? Your computer is not Turing machine.