question for physicists

[Kuciwalker]

Originally posted by KrazyHorse
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

It doesn't matter whether or not we can prove it. As we treat it, the set of halting programs is undecidable*. An undecidable set is one for which there exists no program that correctly decides whether a given element is in the set. A set is decidable as long as such an program exists, even if we can't prove that a given program is that one.

*or rather it's semi-undecidable, because we can determine that a program is in the set but not that it isn't

[KrazyHorse]

I'm asserting that nobody here has demonstrated to my satisfaction that it's necessarily not true, nor that there is any reason outside the fact that the number of computable numbers is countable that it shouldn't be true.

[Kuciwalker]

Originally posted by KrazyHorse
It's not necessarily not.

Actually, you've just proved that it isn't possible for any enumeration of programs to correspond (via the halting problem) to a computable number

[KrazyHorse]

Originally posted by Kuciwalker


It doesn't matter whether or not we can prove it. As we treat it, the set of halting programs is undecidable*. An undecidable set is one for which there exists no program that correctly decides whether a given element is in the set. A set is decidable as long as such an program exists, even if we can't prove that a given program is that one.

*or rather it's semi-undecidable, because we can determine that a program is in the set but not that it isn't

Yes, but this still brings us back to the original question:

Why should we care whether or not there are uncomputable numbers generated by physical systems?

It's neither a necessary nor a sufficient condition to, say, solve the halting problem by physical means.

[KrazyHorse]

Originally posted by Kuciwalker


Actually, you've just proved that it isn't possible for any enumeration of programs to correspond (via the halting problem) to a computable number

???

No, not as far as I can see I haven't.

[KrazyHorse]

Seriously:

can you either demonstrate or provide a reference which does demonstrate the fact that any encoding of an undecidable proposition is necessarily uncomputable?

[Kuciwalker]

Originally posted by KrazyHorse
I'm asserting that nobody here has demonstrated to my satisfaction that it's necessarily not true, nor that there is any reason outside the fact that the number of computable numbers is countable that it shouldn't be true.

1. There exists no program which returns "1" for all programs that halt (on no input) and "0" for all programs that do not halt (on no input). If you want me to prove this I can.

2. Define the number C as the number whose nth digit in its binary represenation is a 1 iff the nth program halts on no input, and a 0 iff the nth program does not halt on no input. Order the programs by "","a","b", etc., discarding syntactically invalid programs.

3. Assume C is computable.

4. From (3) and the definition of a computable number, there exists some program P(n), which returns "1" if the nth digit of C is 1 and "0" if the nth digit of C is 0.

5. I can construct a new program, Q(S), which takes the string S encoding some program, determines the number n corresponding to that program (simple iteration can do this), and returns P(n). Q(S) returns "1" iff S halts on no input, and "0" if S does not halt on no input.

6. Contradiction, because by (1) Q(S) doesn't exist.

7. Therefore C is not computable.

[KrazyHorse]

I might be acting stupid here, because I have very little experience working with the idea of computability etc, but I honestly can't see adequate demonstration of that proposition anywhere in this thread.

[KrazyHorse]

Originally posted by Kuciwalker


1. There exists no program which returns "1" for all programs that halt (on no input) and "0" for all programs that do not halt (on no input). If you want me to prove this I can.

I dispute this assertion.

I accept that either:

a) such a program doesn't exist
b) such a program exists but we cannot know that this program's output corresponds to the solution to the halting problem

[Kuciwalker]

Ok.

1. Let Halt(S) be a program that returns "1" iff the program encoded by S halts on the input S* and "0" iff the program encoded by S does not halt on the input S.

2. There exists a program CONFUSE(S) with the code:

if(Halt(S)) loop forever;
else return;

3. If CONFUSE(CONFUSE) halts it loops forever, and if it does not halt it halts. Contradiction.

4. Therefore Halt(S) does not exist.

* the problem of halting on no input can be reduced to the problem of halting on the input of its own code (and vice versa), so this works.

[KrazyHorse]

Kuci:

Ahhh.

Perfect.

[civman2000]

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.

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

Not really. Given that we have very strong reason to believe that the Riemann hypothesis is decidable, we essentially already can do this (test each p until we get a proof of either the Riemann hypothesis or its negation; as long as it's decidable, this works). Of course, this is so amazingly inefficient that no one actually does it. The only difference that solving the halting problem would necessarily make would be that we would know for sure that our amazingly inefficient theorem-finding algorithm always is guaranteed to work.

[Kuciwalker]

Touche, though our program Halt(S) might be a lot faster than actual execution of S.

[Jon Miller]

KH is suggesting that this is a problem of our mathematics, rather then such a number being not calculateable.

I don't see (but am not a logician or a compute rscientist) where anything has been shown that this is an issue of mathematics or not.

JM

[Kuciwalker]

Well, if we could build a device that was able to successively generate the digits of a non-computable number (by, say, measuring the probability that an electron has spin-up or spin-down to greater and greater precision), we could build devices strictly more powerful than our current theoretical model of the computer. Such a device might be able to do useful things that are currently impossible. It all hinges on whether or not such numbers actually exist in reality, or if the universe itself only uses computable numbers.

That is an empirical question, not a mathematical one.