4 ms·

What would happen if you went through with it? I bet it wouldn't be too hard to write a program that does it for 90% of cases. Is there a simple case that wou

What would happen if you went through with it? I bet it wouldn't be too hard to write a program that does it for 90% of cases. Is there a simple case that would be impossible to determine?

eru 14y ago
Oh, the halting problem is easy enough to solve for most cases (people do it informally all the time), just not for the worst cases. For giving a percentage, you need to specify a distribution of programmes first. E.g. programmes created reading from /dev/random, or programmes downloaded at random from the internet, or something more sensible.
zura 14y ago
Exactly. The first reason to reply to this kind of request would be to engage with the uneducated client, and make sure that she will pay for that 90%.
rcfox 14y ago
Off the top of my head: 1) Assuming rand(x,y) gives a uniform distribution between x and y: for (int a = 0; a < INT_MAX; a += rand(-1,1)); 2) I can't find the source any more, but someone basically implemented a big int library with bit twiddling to allow for an upper bound on a loop that would finish after the heat-death of the universe, assuming generous CPU specs. Not infinite, but also non-terminating. 3) Anything that makes a system call. You might never get scheduled again!
- StavrosK 14y ago
  #2 isn't any more non-terminating than "for (i=0; i < 100; i++)" is.
- dagw 14y ago
  As to 1) any rand() implementation that doesn't use an external source of randomness is deterministic and cyclical, thus it is quite possible to determine if 1) halts by analyzing rand()
kens 14y ago
A simple example that is hard to determine if it halts is to iterate through a,b,c,n and see if a^n+b^n=c^n. I.e. solve Fermat's last theorem by brute force. (I won't spell out the iteration details.) If your software could determine if this halts or not, it would prove Fermat's last theorem. (Obviously since FLT has been proven, this particular case is known not to halt.)
- Luyt 14y ago
  Interesting read: "The proof itself is over 100 pages long and consumed seven yearsof Wiles's research time. For solving Fermat's Last Theorem, he was knighted, and received other honors." http://en.wikipedia.org/wiki/Wiles%27s_proof_of_Fermat%27s_Last_Theorem http://en.wikipedia.org/wiki/Wiles%27s_proof_of_Fermat%27s_L...
- nijk 14y ago
  There is a paper online that proves fermat's last theorem in this way, by exploiting the C compiler's ability to optimize away non-terminating code that has no observable state changes.
nadam 14y 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 14y ago
  I find your code hilarious in that, if it ever terminates, it doesn't print the two primes.
  - pi18n 14y ago
    A true mathematician; nadam only cares that a solution exists.
- tomjen3 14y ago
  That 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 14y ago
    The 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 14y ago
  But 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?

What would happen if you went through with it? I bet it wouldn't be too hard to write a program that does it for 90% of cases. Is there a simple case that would be impossible to determine?

eru 14y ago

Oh, the halting problem is easy enough to solve for most cases (people do it informally all the time), just not for the worst cases. For giving a percentage, you need to specify a distribution of programmes first. E.g. programmes created reading from /dev/random, or programmes downloaded at random from the internet, or something more sensible.

zura 14y ago

Exactly. The first reason to reply to this kind of request would be to engage with the uneducated client, and make sure that she will pay for that 90%.

rcfox 14y ago

Off the top of my head: 1) Assuming rand(x,y) gives a uniform distribution between x and y: for (int a = 0; a < INT_MAX; a += rand(-1,1)); 2) I can't find the source any more, but someone basically implemented a big int library with bit twiddling to allow for an upper bound on a loop that would finish after the heat-death of the universe, assuming generous CPU specs. Not infinite, but also non-terminating. 3) Anything that makes a system call. You might never get scheduled again!

StavrosK 14y ago
#2 isn't any more non-terminating than "for (i=0; i < 100; i++)" is.
dagw 14y ago
As to 1) any rand() implementation that doesn't use an external source of randomness is deterministic and cyclical, thus it is quite possible to determine if 1) halts by analyzing rand()

kens 14y ago

A simple example that is hard to determine if it halts is to iterate through a,b,c,n and see if a^n+b^n=c^n. I.e. solve Fermat's last theorem by brute force. (I won't spell out the iteration details.) If your software could determine if this halts or not, it would prove Fermat's last theorem. (Obviously since FLT has been proven, this particular case is known not to halt.)

Luyt 14y ago
Interesting read: "The proof itself is over 100 pages long and consumed seven yearsof Wiles's research time. For solving Fermat's Last Theorem, he was knighted, and received other honors." http://en.wikipedia.org/wiki/Wiles%27s_proof_of_Fermat%27s_Last_Theorem http://en.wikipedia.org/wiki/Wiles%27s_proof_of_Fermat%27s_L...
nijk 14y ago
There is a paper online that proves fermat's last theorem in this way, by exploiting the C compiler's ability to optimize away non-terminating code that has no observable state changes.

nadam 14y 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 14y ago
I find your code hilarious in that, if it ever terminates, it doesn't print the two primes.
- pi18n 14y ago
  A true mathematician; nadam only cares that a solution exists.
tomjen3 14y ago
That 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 14y ago
  The 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 14y ago
But 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?