question for physicists

[Kuciwalker]

btw, if we could solve the halting problem, most of mathematics would become trivial. For example:

String p = "";
while(p is not a valid proof of the Riemann hypothesis) p = next(p);
// next(p) generates the next string after p, e.g. ""-> "a", "a"->"b", etc.

Answering the halting problem on that program answers the Riemann hypothesis.

[KrazyHorse]

That number C is noncomputable because if it were computing the halting problem would be decidable

I don't see that.

[Kuciwalker]

Originally posted by KrazyHorse

That number C is noncomputable because if it were computing the halting problem would be decidable

I don't see that.

If it were computable then to solve the halting problem for the Nth program I'd just have to compute the Nth digit of C.

[KrazyHorse]

Originally posted by Kuciwalker
btw, if we could solve the halting problem, most of mathematics would become trivial. For example:

String p = "";
while(p is not a valid proof of the Riemann hypothesis) p = next(p);
// next(p) generates the next string after p, e.g. ""-> "a", "a"->"b", etc.

I understand that.

Now, let's use your example:

1 is generated if the program halts, 0 if it doesn't.

Now, are you going to tell me that "the number which is generated by this algorithm" is non-computable?

It's either 0 or 1, and they're both computable

[KrazyHorse]

Originally posted by Kuciwalker


If it were computable then to solve the halting problem for the Nth program I'd just have to compute the Nth digit of C.

Just because you don't know how to compute something (or can be shown to never know how to compute something) DOES NOT PROVE that the number generated is non-computable.

[Kuciwalker]

No, the number whose digits are the answer to the halting program for all programs. If program 1 halts, the first digit is a 1, if program 2 doesn't halt, the second digit is a 0, etc.

[Perfection]

Well, the number is which fraction of programs within some constraint (say input code length or some such) halt (as opposed to run forever). With certain programs there is no mathematical analysis or computation that allows one to discern whether it will halt or not and so to evaluate this fraction completely under certain circumstances becomes impossible.

[KrazyHorse]

It could turn out that the halting problem for some encoding of programs is the binary representation of pi. Is pi therefore non-computable?

[Kuciwalker]

Originally posted by KrazyHorse
Just because you don't know how to compute something (or can be shown to never know how to compute something) DOES NOT PROVE that the number generated is non-computable.

Yes it does. There exists no algorithm to decide the halting problem for a program. If there were an algorithm that generated the digits of C, we could modify that algorithm to produce an algorithm to decide the halting problem for any program. Therefore there is no algorithm that generates the digits of C, therefore C is non-computable.

[Kuciwalker]

Originally posted by KrazyHorse
It could turn out that the halting problem for some encoding of programs is the binary representation of pi.

That's not necessarily true.

[KrazyHorse]

Originally posted by Kuciwalker


Yes it does. There exists no algorithm to decide the halting problem for a program. If there were an algorithm that generated the digits of C, we could modify that algorithm to produce an algorithm to decide the halting problem for any program. Therefore there is no algorithm that generates the digits of C, therefore C is non-computable.

NO!

There are two possibilities:

1) C is non-computable
2) The proposition that a computable number C corresponds to this definition of C is not decidable

[Kuciwalker]

A related noncomputable number, the halting probability, can also be used to solve the halting problem.

xpost

[Perfection]

Originally posted by KrazyHorse
It could turn out that the halting problem for some encoding of programs is the binary representation of pi. Is pi therefore non-computable?

That would be a crazy cowinkydink!

[KrazyHorse]

Originally posted by Kuciwalker


That's not necessarily true.

It's not necessarily not

[Perfection]

Originally posted by KrazyHorse


It's not necessarily not

You're asserting that some sort of coincidence may occur with some calculateable number which would be infinitely improbable.