question for physicists

[KrazyHorse]

Re: Re: Re: question for physicists

Originally posted by Kuciwalker


The issue is that if physics includes non-computable numbers, that violates the Church-Turing thesis (the computational power of the universe is equivalent to the computation power of a Turing machine, which is a theoretical model of a computer). If that's false, we can harness these non-computable numbers to pretty dramatically increase the computational power of real computers.

Errr....given that any physical quantity can only be measured with finite accuracy in finite time, I don't see how.

[KrazyHorse]

also, given that the rationals and thus the computable numbers are dense in the reals, of course...

[Kuciwalker]

Computable numbers only have to be measurable to a finite accuracy in finite time.

[KrazyHorse]

Yes, so I don't see how you would be able to tell the difference between a physical system which has a measurable quantity which is computable and one which is non-computable.

[KrazyHorse]

To be continued, by the way. I'm being pestered to go for a walk.

[Perfection]

Originally posted by KrazyHorse


On the contrary, all real numbers are computable. What is undecidable is whether a given real number corresponds to a definition you've chosen to give to it...

My wikipedia link says otherwise.

[civman2000]

Back to the original question, it seems that at least in some sense the answer should be yes. The computable numbers are dense in the reals and closed under every operation imaginable (ie computable). Thus if the laws of physics involved some noncomputable constant, we would have no way of knowing: for any property of such a constant that we could discover through a finite amount of measurement, there is some computable constant that has the same properties. After all, there are all sorts of seemingly arbitrary constants in physics. For all we know, some of them might be noncomputable, but we have no way of ever finding out.

EDIT: Yeah, basically, what KH said.

[Kuciwalker]

Originally posted by KrazyHorse
Yes, so I don't see how you would be able to tell the difference between a physical system which has a measurable quantity which is computable and one which is non-computable.

If you knew a priori that the system necessarily generates a non-computable number. (How that would occur I don't know, but it doesn't strike me as immediately impossible.)

[civman2000]

Re: Re: Re: Re: question for physicists

Originally posted by KrazyHorse


Errr....given that any physical quantity can only be measured with finite accuracy in finite time, I don't see how.

Ah, but if we knew some physically measurable constant C encoded the solution to the halting problem, we could use it to solve the halting problem: given the nth Turing machine, we just measure the nth digit of C to find out whether it halts, something which is impossible to do by a formal mathematical algorithm.

[Kuciwalker]

Re: Re: Re: Re: Re: question for physicists

Originally posted by civman2000
Ah, but if we knew some physically measurable constant C encoded the solution to the halting problem, we could use it to solve the halting problem: given the nth Turing machine, we just measure the nth digit of C to find out whether it halts, something which is impossible to do by a formal mathematical algorithm.

At least, impossible to do by a formal mathematical algorithm run on something with the computational power of a Turing machine

[KrazyHorse]

Originally posted by Perfection
My wikipedia link says otherwise.

Yeah, I was confused about the definition of computable.

[KrazyHorse]

Re: Re: Re: Re: Re: question for physicists

Originally posted by civman2000

Ah, but if we knew some physically measurable constant C encoded the solution to the halting problem, we could use it to solve the halting problem: given the nth Turing machine, we just measure the nth digit of C to find out whether it halts, something which is impossible to do by a formal mathematical algorithm.

I don't understand what you're saying here. I have very little training in theoretical computer science...

[Kuciwalker]

The halting problem is the problem of deciding if a given program eventually terminates on a given input. It's undecidable, and by extension most useful questions we could ask about programs are undecidable. Given a number C whose binary digits were those programs that halted on some input (it could be no input, it could be the code of the program, etc. - they're all essentially equivalent) in some order, we could solve the halting problem simply by measuring C to the necessary precision to confirm that digit.

Of course, for a number like that to occur seems a bit unlikely, but other numbers could give use the same power.

[KrazyHorse]

So you're labeling all possible programs with a number from 1 onwards (where 1 is the "hello world" program and upwards in some increasing complexity or something). All these programs are run, and the binary number C has digits corresponding to the termination of the program.

Now, my question is, what does noncomputability have to do with this?

[Kuciwalker]

Originally posted by KrazyHorse
So you're labeling all possible programs with a number from 1 onwards (where 1 is the "hello world" program and upwards in some increasing complexity or something). All these programs are run, and the binary number C has digits corresponding to the termination of the program.

Now, my question is, what does noncomputability have to do with this?

That number C is noncomputable because if it were computing the halting problem would be decidable (and it isn't).