Re: Undecidability in Physics

LauLuna wrote:
I propose the following question:

Is there any logical reason to reject the possibility of a physical
theory PT enabling us to calculate the temporal development of any
finite physical system for any finite period of time?

By 'logical' I mean, inter alia, not due to quantum uncertainty.

For example, can we use Turing's theorem to that effect? A Turing
machine can be realized as a finite physical system. If PT exists, then
we can calculate the behavior of any Turing machine under certain
idealizations like unbounded supply of time and energy, etc. It appears
that of that calculation were always possible on the basis of our
knowledge of the physical features of the machine, the halting problem
would be solvable.

If PT is a physical theory in the classical sense, i.e. consisting of
laws that computably map any instant tn of any finite physical system
into tn+1, then PT should be able to work under those idealizations.
Consider that no actual infinite would have to be involved; the so
called Busy Beaver shows (informally) that the function S: N->N, which
takes the number of bits required to describe a Turing machine and
returns the largest number of steps it can run before halting or
looping, is uncomputable. This follows easily from Turing's theorem.

K. Svozil suggests the existence of a physical undecidability of this
kind in
http://tph.tuwien.ac.at/~svozil/publ/casti.htm#bernstein#bernstein

I think there is something missing here. A contradiction of Turing's
theorem would arise only if there existed, in addition to PT, an
algorithmic procedure for obtaining a sufficient physical description
of any physical Turing machine, out of its computational description or
by means of empirical observation. Could the logical impossibility lie
here?

Regards.


It is because there is no (general) procedure as Svozil mentions.

"As a comfort to those who conceive the "Cartesian prison" as the
source of all problems, one could cite a nice theorem by Gold [24].
It is sometimes referred to as the recursive undecidability of the
rule inference problem: For any mechanistic intelligence/agent A,
there exists a total recursive function f such that A does not
infer f. In more physical terms, there is no systematic way of
finding a deterministic law from the (input/)output analysis of a mechanistic physical system.

An informal way to (algorithmically) prove Gold's theorem uses
the halting theorem. Suppose that it would indeed be possible to
derive laws systematically. Let us call this agent or computable function RULE. RULE would have to watch the behavior of the system
it analyzes. But any complete analysis would require the observation
of TMAX(n), where n is the minimal description size of the system.
Since TMAX(n) grows faster than any computable function of n, RULE cannot be computable.

So, even if we would be in a "God-like" position and would be disentangled and freed from the observed system, we would have to
cope with the fact that there is no systematic way of deriving
causal laws.-Indeed, we may safely state that, except for the most elementary phenomena, deriving causal laws remains a rare art!"

http://www.cis.udel.edu/~case/colt.html
John Case's COLT Page
"Consider the problem of finding a rule for generating a sequence
of numbers such as 9, 61, 52, 63, 94, 46, 18, 1, 121, 441, ... .
Here is a rule for this sequence. First compute the squares of successive integers beginning with 3, but, then, to generate the sequence, use, in place of these squares, the squares each with its decimal digits written down in reverse order(ignoring any lead zeros). N.B. This rule can be written as a formal algorithm (or computer program). The problem of finding such rules gets harder as the
sequences to generate get more complicated than the one above.
Can the rule finding itself be done by some computer program? Interestingly, it is mathematically proven that there can be no
computer program which can eventually find (synonym: learn) these (algorithmic) rules for all sequences which have such rules!"

SH: These two quoted sources seem to be in agreement, perhaps I
didn't understand your question, are you agreeing with Svozil?

"In short: reasonable (consistent) theories predicting the future behavior of arbitrary mechanistic physical systems are impossible.
So, if one beliefs [SH: believes] in the physical relevance of the
model of universal computers, then no physical theory can predict
all the physical phenomenology. In particular, there are certain physical prediction tasks which are undecidable." (Svozil)

SH: If one assumed the universe was a computer or arose from a
Cellular Automata (CA) unfolding the behavior of its rule over
billions of years, then to the degree that the restrictions on computability (halting) precisely reflected the true operations
of the universe as mathematical functions, then applying such
properties would be relatively isomorphic. But at this point
there is insufficient evidence that the universe is a computer
or that Computationalism, a correct program running on a digital
computer can instantiate a human mind. IOW, no proof that because
a PC can perform some tasks that a human can, that it can perform
all tasks that a human mind can, esp. non-algorithmic processes,
if there are such. Albeit there may be close approximations.
Penrose failed when he attempted to use Incompleteness to disprove
AI, and neither can Incompleteness be used to prove AI is possible.

AI in the strong sense,
Stephen
.

Relevant Pages