[Universal computation isn't universal] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Universal computation isn't universal
(Click here to view the original thread with full colors/images)
Posted by: Todd Heywood
Here's a paper that points out that the Church-Turing thesis is a myth:
http://www.cse.uconn.edu/~dqg/papers/cie05.pdf
Bascally, the myth is that "computation" is limited to evaluation of functions. It isn't.
There is a good body of work on this subject... one place to start is...
http://cs.brown.edu/people/pw/
Obviously, a New Kind of Computation (NKC) has repercussions for NKS.
Posted by: Tony Smith
Wow! That makes a lot more sense of things that were starting to look difficult. I was even around in the early days of "Theory of Computation" and can recognise caveats that the whole focus on Turing "universality" has been blindly ignoring.
What is now a lot less surprising is that our simplistic CAs et al, being interactive rather than functional, have relatively little trouble attaining functional universality, but still don't produce any real progress on modeling the interactive universality of the world we find ourselves in.
What seems to be at stake is the assumptions of functional determinism which permeate NKS/"digital philosophy", but which were not quite so intrinsic to the more general study of complex systems which gave birth to NKS. Did we throw the baby out with the bathwater and leave ourselves holding a plastic doll?
Seems the goal posts just moved back to where they always should have been.
Posted by: Jason Cawley
This was thoroughly discussed the NKS Brown program 2 years ago. The claim that a larger space is reached by an interactive computation only holds if the open channel conveys infinite information at each time step. Otherwise, it is always possible to encode the interaction information as another part or aspect of the initial condition, and you reach exactly the same space of computations. The idea is still a useful one and led to the ICA set up, which is essentially the machine with input form of a CA. These may be a more natural model for some processes - and you can find several threads on this forum about them. But the broader claim rests on a cardinality argument that does not withstand scrutiny, since real systems do not receive an infinite information input from their environments in finite time.
Posted by: Todd Heywood
Yes, but that is a critique limited to one particular model of sequential interactive computation (single agent, or observer-environment) proposed as an alternative to the Turing model. This is an extension of the Turing machine and is thus still based on function evaluation.
In my opinion the value of the paper cited is to point out the myth of the Church-Turing thesis, and thus to raise the question of whether "computation" is possible which is not based on functions.
For example, relations are not functions. And process synchronization in parallel/distributed systems achieves coordination without fitting the functional input/output picture.
The point of this paper should be to stimulate thinking on new possibilities. Sequential, single-agent interactive computation is just a baby step beyond Turing machines, and its particular limitation does not imply that interaction is practically the same as function-based computation.
Posted by: Tony Smith
The claim that a larger space is reached by an interactive computation only holds if the open channel conveys infinite information at each time step.
I'll get back to "infinite" in a moment, but clearly each node (assuming a graph-theoretic bottom level) receives unlimited input at each computation because there are no bounds, recursively, on where its neighbourhood received its inputs from.
The persistence of the "in an infinite universe everything will occur many times" myth shows that even genius-level mathematicians more often than not fail infinte cardinality, to a degree that is only comparable to religious obsession.
Just from what has been said here it should not be hard to see that the effective input to each computation has cardinality of order ℵ₁—strictly uncountable.
Posted by: Jason Cawley
No, sorry, connection to everything else does not imply continuum infinite cardinality. First and the most minor point, the argument as structured begs the question, by assuming the rest of the universe is infinite. If it isn't, then naturally the information reached that way is as bounded as the universe itself. This shows only that the argument of relatedness is at best only half what would be needed, and the minor (infinite nature) has to be assumed independently.
But the argument is weaker still because even making that assumption does not establish the conclusion. The reason is an information channel is measured in units of information per unit time, not units of information, absolutely. And it is the capacity of the channel in this sense, not the total information that eventually flows through that channel, that needs to be infinite, in order for a system in interaction to reach any larger space than the computables. Otherwise I am just getting the time dimension's infinity running down the page, with the addition to it at each time step bounded on the right. The amount of that input can vary with time, it can grow with time, and the conclusion still does not follow. It needs instead to be strictly infinite off to the right at some time.
Otherwise I can just treat it as another variable in an initial condition, and pair the two dimensions up into a single (larger, to be sure) number with a pairing function e.g., and the possibility space can still be put into one to one correspondance with the integers by running through all such paired up initial and interaction condition bundles.
And the same is true for any system with stochastic inner workings. As long as only a bounded number of finite bits are randomized, not over the whole evolution but per single time step, I can treat that whole sequence of "coin tosses" as another variable in the initial condition, specify them beforehand with an external sequence that "calls the tosses", pack them into an integer variable, pair up as before, etc.
Some quantum computing advocates have claimed that access to continuum multiway paths and averages over them, might create a computational system that accesses higher cardinals. But the best QC operatives, the ones most careful with their analysis, do not make this claim. Because as soon as a basis is chosen and the calculation ends, countable covers drop us back into computable-land. The most that they claim for QC is that some Turing computations might be completed in finite time, that would run forever on a classical computer. And in practice, they generally claim weaker multiway speed up of some exponential computations to polynomial time.
The usual understanding of information channels effectively exploits locality to tame distant interaction. Say you have a bounded region X and wish to consider it in isolation from the remainder of the universe. You make the behavior inside conditional on (a function of, same thing) the existing state within X, the physical laws, and the flux of information across its boundary x. There is undoubtedly some varying Y beyond the boundary layer that affects what happens within X. But you incorporate that - already combined with whatever effects propogate from Z to Y beforehand, or from Z to the boundary layer - into the general variation in the boundary layer x. To do so all you have to do is let x vary in all the ways it might. You have then included all the variations in the rest of the entire universe that will matter for X, without needing to or pretending to now the whole history of the rest of the universe.
A slightly tangential issue - philosophers notice a tendency of arguments to say, in effect, you can't know anything unless you know everything, because everything is connected to everything else. This is a well known fallacy. It does not follow. For unknowns to vitiate one's knowledge of the known, it is not enough that they affect the known and are unknown themselves. If their possible modes of impact can be analysed or covered and included in the claims made about what is known, they indeed affect the subsystem you are considering, but do not prevent your knowledge of it.
As for the claim that relation is more than function, I think this is more a matter of preferences about foundations of math or logic than anything else. A r B can be viewed as a primitive, or as a function r of two variables A and B. Notice, that is not remotely saying B is a function r of A. Relations multiply variables when incorporated in a functional set up. But they can be so translated. If you have a truly infinite set of relations, then and only then cardinality issues can, but do not always, enter.
Relating two infinite sets to each other with complete generality (no limiting form or simplicity on the relation allowed) is the paradigmatic way to get to a continuum cardinality from countable ones. Peirce called continuum simply relational generality, e.g. you power set the integers. Mathematicians still have no trouble at all with functions over uncountable sets. When those functions are restricted to well behaved ones in various ways (e.g. continuity, which gives an effective boundedness in one direction by making some details too small to matter), they are "tamable" back to calculation again. (Much of analysis is precisely the set of formalisms for doing so).
I believe however that the whole line of thought suffers from another difficulty. It too readily equates the computable with the simple. Many of the arguments used were favorites of philosophers like Popper, arguing for indeterminism as he called it, but can more accurately be said to be aimed at predictability. Predictability and computability are separable, because many computations are themselves intractable - computationally irreducible.
The bar to effective prediction comes up much sooner than the whole line of argument supposes. And phenomenal or thought-experiment arguments against predictability therefore do not reach the issue of computability or its absence. Otherwise put, NKS informed Church-Turing subscribers are in no way committed to a predictable nature, and indeed insist that in general it isn't. Only predictions of pockets of simplicity and general (coarse) facts about the rest can be expected, even of a computable universe.
I also note, because I mentioned Popper on indeterminism, that determinism and computability are also separable. As mentioned earlier, stochastic systems fit just fine within the computable framework, provided the amount of randomness added to subsystems per unit time is bounded. Statistical randomness is actually perfectly compatible with prediction when suitable average characteristics are all that is wanted, as every practioner knows. But even in a sensitive randomized setting, in which no such average helps and prediction falls, computable models are readily possible. Which then fully capture the empirical sensitivity and unpredictability seen, without departing from computability.
This leads to the following challenge or question. We all know how to put more gunk in our models - higher cardinals and continua, randomness, external interaction, infinite universes, discontinuity, sensitivity, dynamic rather than fixed laws, etc. But what empirical motivation is there supposed to be for doing so? Models are not designed to wallow in mystical ignorance before the unfathomable, but to achieve knowledge where it can be achieved, while being true to phenomena. So, what is it in the phenomena themselves (not theories of them, or modeling methods favored by this or that existing school, or philosophical desires or preferences), that supposedly requires models specifically beyond the computable?
It is not predictability failure, because that is compatible with computation. It is not observed sensitivity, because that is compatible. It is not "multi-valued-ness" or indeterminism, observed or posited, because each is compatible. It is not changing the rule applied through time, because that is compatible. What is it supposed to be?
I've heard the argument from some that it is the algorithmic randomness of this or that aspect of nature. But this mistakes something we know theoretically about sequences in general, for an observable. In a mathematical sense, most sequences are algorithmically random. But it is in general formally undecidedable whether any given sequence is the output of a computation, and if so how soon it appears in this or that enumeration of rule types and initials. So what observable, or general aspect of observables, is supposed to force me to move beyond the hypothesis, "this observed sequence may have been produced by a computable process, a rule and initial pair, that I simply haven't yet found"?
I should add a few comments on what I do think can be learned from this line of thinking. I have been interested myself in extending NKS type systems to include modeling aspects distinct from the straightforward local single path determinism with anything that matters off in a detail of the initial condition. Partially from philosophical motivations, to see what is separable and the like, but largely because I consider such set ups more natural models of some social science systems. While staying within the computables, and the idea of modeling systems with computer programs as outlined in NKS. I am grateful to Peter Wegner in particular for helping raise the issue of open sytems. Ashby's classic scheme of machines with input was the other main influence on the idea of ICAs, while incidentally Todd Rowland came up with the code for them when I described them.
Before that, Paul Davies had ideas about "downward causation" that he explored with Wolfram, resulting in the GCA idea. Working on both I noticed that GCAs are a proper subset of the ICAs - an external interaction sequence can always be found that gives the same "switches" and thus the same behavior. Though the GCA set up may be a more plausible model for how such switch sequences occur, in some empirical system. E.g. traders all reacting to a centralized and averaged, but endogenous, price. At the same time, Seth Chandler has worked on NKS systems on networks, motivated by a desire to approximate social systems more naturally and accurately.
What such set ups show is the space of behaviors reached is the same, the computables. But for many real systems they may also be more natural models. So by all means, look at systems in interaction, or sensitive to global variables, or containing stochastic aspects or multiway evolution, or networked rather than regular arrayed, etc. All that is still computable and still NKS.
Posted by: Tony Smith
Jason, your comments could easily be taken as implying that "computable" is of marginal utility and we might as well just get on with what we were doing before it intruded. I certainly don't want to go that far, but find a hurdle at the fact that a computation cannot be sensibly defined when its inputs are in the limit unknowable.
The notion of "bounded regions" does not sit rigorously with an underlying graph-theoretic structure in which the discrete elements (nodes, links) are impermanent and continuity of detailed structure is only evident at an emergent level. Quantum entanglement strongly suggests fundamental nonlocality.
Separately, you are still ducking the clear distinction that must be made in notionally finite yet unbounded systems between those with countable/polynomial and those with uncountable/exponential growth. Supposed one-to-one mappings from the latter to the former are disingenuous.
For me the question has become how might our resilient, conservative, diverse and largely computable cosmos have emerged from less constrained interaction at a more fundamental
level? I'm getting closer to being able to show qualitatively that such emergence may be effectively unavoidable, but that is a topic for another day.
Posted by: Jason Cawley
I don't see that I am devaluing computation in any way. On the contrary, I'm claiming we have no evidence that the computables as such are smaller than accessible reality. I think all the interesting stuff happens within the computables, and that reaching for regions supposedly beyond them (mathematically definable, certainly) is not scientifically or physically necessary. Speculatively possible perhaps, and we are free to wonder about them and see where they might make our formalisms simpler. But where they don't, and while we know computables suffice, I don't see the need.
As for being ill at ease with a notion of computation whose inputs might be unknowable in the limit, the function x+1 applies to infinitely many integers but we all know what it means. A mere infinity of that simple a form should not bother anyone. I do think cardinality issues are a distraction rather than fundamental to real complexity. But that is an argument against seeing continuum cardinalities in open systems, not an argument in favor of it.
Why do I think cardinality issues are something of a distraction? Because I notice all our actual computers and all the actual computations we do with them, are strictly finite, not even countable. When we construct them such that they could, in infinite memory and infinite running time limits, perform any computation, we find in practice that with large but finite memories and a large but finite number of operations or cycles, they can do anything we can see as do-able at all. While also seeing a whole space of undoables, of the character "take way too long", beyond.
Thus it seems to me the thing we have mathematically understood as universality (that makes use of countable infinity), corresponds to something real and useful in finite practice, that I like to call programmability. And all the real computation nature does around us and that we do ourselves, seems to be of this "finite programmability" type. But all of that is my own philosophical addition or diagnosis of what is going on - my hunch that in fact we don't even need the one lowest infinity the formal theory of computation makes use of. And I don't see us having, or needing, two orthogonal infinities in arbitrarily general relation to each other.
The point about bounded regions is well posed, but I think readily addressed. One can translate it to graph-theoretic terms by saying the number of connections outside a locally well connected region will be bounded above. One can formulate the second part by the effect of single cuts on measured distance. Then a "mostly local" graph will not see exponential increase in the number of "distant" connections with r. Yes we observe some non-locality. But we also observe gobs of locality, not all-to-all universe-wide direct connection. Everything may be connected to everything else, but mostly by going through intervening nodes. If the number of distance connections is bounded, then there still will not be infinite information channels to local nodes.
I deny I'm ducking anything when I insist on finiteness rather than continuum infinities. And I deny exponential increase maps to uncountables while polynomials map to countables. When bounded, both map to "finite". When not, both map to "countable". To get to uncountable you need not relation alone, which is enough to give exponential increase, you need relation without simplicity (e.g. continuity) over multiple actual infinities. Reality as constrained by dynamics I expect to be finite, and smaller than abstract possibilities, thought of as relational power sets and thereby exponentially growing with the number of elements. I also do not conflate polynomial with smaller than exponential, because polynomials can have huge leading terms and small exponentials are perfectly tractable. n is not always large.
I agree that one can consider less constrained interaction at a more fundamental level. But there is no requirement to do so. If it results in a simpler formalism, great. We will all undoubtedly believe in the computational aids it invokes, and have decent philosophical reasons for doing so. But accessible, measureable reality is finite for us, and all any theory is required to reproduce. If some theory does so without invoking any infinities at all, great. It some theory does so invoking only the countables needed for computation, fine. Nobody is going to prove that more is needed, because we have finite observations to map and it is formally undecidedable whether they may have come from a rule-initial pair in an entirely computable way.
But somebody might make more plausible what they can't prove, by giving us a truly elegant and compelling description of the phenomena that invokes higher cardinals along the way. So far, we instead have elegant theories of that description that dramatically underspecify experience. As we push to unify them they cease to possess any real elegance, while requiring greater and greater departure from observables, and promising to tell us less and less about the specific reality (as opposed to generalized possibilities) we actually experience. They shade off toward telling us that anything could have happened while something apparently did, maybe lots of somethings. Which is simply not helpful. Please note the last only applies to the push to unify, simplify, and account for everything - at the base level of underspecific description of experience, existing theory is wonderful. Where it is properly modest in its knowable claims, it is the best we've ever had; where it drops that underspecifying modesty to push for everything it falls apart, philosophically speaking.
The hope is that an operationally sound and still computable model can do better. That remains to be seen, but there are no compelling arguments out there that continuum infinite cardinality helps. And certainly there is nothing in Wegner's recent article that shows it is physically real, or even that shows his preferred open and interactive systems actually reach it. In fact all the aspects he considers unreachable by computations as usually defined, are entirely reachable by computations as usually defined (persistence, ongoing interaction with external environment, dependence on previous steps, asynchronous updating, etc).
Posted by: Tony Smith
Jason, I'll only persist on the areas of divergence. Most of what you are saying, especially the "gobs of locality", just underlines the reason NKS remains relevant to the unfashionable quest for a credible qualitative theory of everything which is smart enough to admit that anything mathematically rigorous must necessarily be a long way further down the track.
Introducing "continuum" is using words I didn't say and only justified in the unlikely event that Canor's Continuum Hypothesis holds. http://www.ii.com/math/ch/ provides a better overview than I can here. However, exponential alone can be shown to get you to Cantor's c (aleph 1) which is most likely larger than the number of ordinals. Combinatorics is asymptotically ordinal and that is at the heart of why I remain unpersuaded by arguments which rely on finitude.
By devaluing computation, I am concerned that it is being weighed down with so much that it ceases to say anything meaningful.
I'm also increasingly of the opinion that the smallest observables are further removed from the fundamental graph-theoretic level than humans are from atoms, so I'm not expecting to find that the ingredients that are currently called "fundamental" are anything more significant than what was able to survive sufficient unconstrained interaction. More usefully, it does not seem to be too hard to show that something like the world we find ourselves in is sufficiently likely to emerge from such a scenario, but that story is going to require experiments with candidate models far below any level we can infer directly from observations ... hardly surprising given the history of science.
Posted by: Vasily Shirin
The very notion of universality is based on idea of infinite
resources available to computer. If Universe if finite, you
cannot even introduce the idea of universal computation
having any practical meaning. Emulation of
one machine by another may require significantly more resourses -
so, it would be wrong to say that rule 110 can emulate
any computation. The idea of Universe-is-a-Computer, therefore,
IMPLIES infinite universe (or else we couldn't utilize the notion
of universality). However, if it's infinite, we cannot call it simple,
and the assertion that simple rules generate complex behaviour is
wrong - in this case, the possibility of complex behaviour is
preconditioned by existence of something of infinite complxity -
namely, infinite Universe.
[ Upon re-reading my message, I found out that what I wanted to say
is in fact contained already in the first sentence].
Posted by: Jason Cawley
Strangely enough, we do not have to create entirely new computer chips from scratch, using a different and dedicated design, every time we want to perform a different computation.
Instead we design chips that execute only a modest instruction set, then we arrange for that instruct set to be universal. No chip has infinite memory, nor does it run for infinite time. But this in no way prevents a limited instruction set from mimicking any computation we care to give it, by just changing the order of a fixed set of primitive operations and repeating those it needs to repeat.
Making the rest software, rather than hardware. By changing initial memory conditions, we can get the computation being performed to match any we specify in some higher level language that is easy for us. The rest is translation and readily performed with finite resources. A computation that is intractable in the higher level language is still intractable when implemented this way, but we can make as much progress as our memory and cycle resources allow, on the same set of problems. Without the language used or the finite and fixed nature of the underlying instruction set mattering much at all.
We find in practice, in other words, that computational universality in the ideal limit, corresponds directly to computational flexibility and expressiveness in finite resource reality. In nearly all practical contexts, we can ignore the difference and speak of universality in our practical processor architectures and programming languages, and in fact computer scientists routinely do so.
I bother to call this programmability rather than universality, when in the strictly finite context, simply to avoid confusions and distractions arising from cardinality arguments. I do so only when the subject is theoretical issues likely to become confused otherwise. Nothing essential to practical computing is involved in those largely theoretical, philosophical, and at times frankly sloppy, arguments and confusions. Everything essential to a pentium chip or to a language like C occurs beyond a flexibility divide, but on this (finite) side of the cardinality divide. And a universal simple program like rule 110 or a universal TM, is programmable in exactly the same way they are.
Posted by: Tony Smith
This thread started with a suggestion as to why interactive hardware might achieve qualitatively more than a TM. CAs appear to me to be a perfectly good example of interactive hardware. It is also abundantly clear that an arbitrary CA is much more likely to produce interesting results than an arbitrary TM.
Wolfram apparently expects that the software running whatever is the fundamental hardware of physics will be quite simple, albeit very difficult to identify. I can only presume one reason for him thinking that is the same as mine ... that any requirement for the scale of software we routinely use to tackle marginally interesting tasks with our general purpose processors would open the doors to the Intelligent Design IDiots et al.
I suspect this discussion has lost a lot of the sense underpinning NKS's claims about universality and the PCE. I understand Wolfram as wanting to show that there is no magic. The whole TM route was a way to show that if very simple parallel hardware (a CA) running very simple software (Rule 110) can potentially do anything a universal computer can do then the universe of simple programs warrants being treated seriously as A New Kind of Science.
It certainly does not threaten the thrust of that argument if interactive systems are inherently more capable than universal computers. And it may shorten the no doubt still challenging route to a NKS-based story which credibly accounts for the world we find ourselves in.
Posted by: Dan Ellwein
"I can only presume one reason for him thinking that is the same as mine ... that any requirement for the scale of software we routinely use to tackle marginally interesting tasks with our general purpose processors would open the doors to the Intelligent Design IDiots et al."
Tony
Why do you feel the need to use the word - idiots...
I don't understand that...
If you want to not give room to the notion of intelligence, then fine...
Why are folks idiots if they choose to believe in a little thing called - intelligence...
I certainly have no desire to call you an idiot because you want to rule out intelligence...
maybe I shouldn't be offended by your post, but I am...
other than that...
what you had to say I thought was really good...
Dan Ellwein
Posted by: Jason Cawley
Can it, people. Last warning. That subject has been aired and it is closed. Go fight someplace else.
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings