All physically realizable computing machines are signal processors - which Turing called C-Machines. None of the TuringMachine limits apply to C-Machines. They apply to A-Machines which are not physically realizable.
- One thing about C-machines to consider is what to expect from putting them in some obvious environments. A C-machine which communicates only to an A-machine as its environment is quite obviously exactly as powerful as a single A-machine (well, assume both are UTMs, for simplicity) consisting of the combined states of the two machines. Next put a C-machine in an environment where it is communicating with an external oracle. Ta da, obviously you've just turned a C-machine into an O-machine. Etc. So I always thought it was clear that he left this unaddressed just because there was little to say about it. It can gain power if its environment is a more powerful kind of machine, otherwise it can't -- but other than that, it's just an A machine; the question of the environment just complicates things, so he left it out for A machines.
- I'm afraid the cart is before the horse. If I understand you, you want to simulate a C-machine on an A-machine; to do this you must simulate a source of signals external to the A-machine. But signals are not information - information is a quantization of signals within some exformal context. Such a classification, while obviously a computational process, is only available to a C-machine.
- Translate this into standard terminology (i.e. eliminate "exformal") and let's see what we're talking about. If the issues is about infinite precision analog, that's not physically realizable. If you're talking about things that are not physically realizable, then there a lots of machine models that are more powerful than Universal A machines, but it's not entirely clear where you would go from there.
- I have in mind a model like this:
- State is represented entirely by phenomena external to the computing device. These phenomena are quantized by an empirical process generating a fixed size finite length binary string called the stimulus. The bits of the stimulus explicitly represent a measurement and all necessary parameterization of the empirical process. This may include combinatorial, historical, and structural context of the empirical process. The width of the input string is fixed by pre-determining the representation of ontologies and resolution limits necessary to the empirical process and the intent of response.
- The C-machine generates a new fixed size finite length binary string of response bits. The width of this string need not be identical with the width of the stimulus string. Each response bit is generated by an ESOP (Exclusive-or Sum Of Products) on the values of the input. The response bits are externally de-quantized to affect the empirically sensible state of the external phenomena stimulating the machine.
- Obviously the function this device computes depends on the empirical process and the phenomena external to the device. Also, obviously, the device is physically realizable. In degenerate form, an AND gate is a realization of such a model. If you can show me how you'd model this on your A-machine, I'd understand what you're saying a lot better.
- I'm confused: "understand what I'm saying"? You're talking about an AND gate. You know an AND gate can be simulated on an A-machine. This therefore is extremely puzzling. (I.e. "huh???")
- The degenerate form is an AND gate hooked up by D/A to sensors and actuators, but I think this model should be sufficiently general to describe any realizable signal processor, including VNA machines, interferometers, you name it. This is also obviously a behaviourist model. Your A-machine is trivially capable of implementing an AND function, but trivially incapable of implementing an AND gate.
- I'm still not getting it. The distinction you're making between AND function and AND gate in this context is...what?
- Because the C-machine interacts, it need not represent nor store state, nor maintain internal loops, but simply classify and recombine signals. The A-machine cannot classify nor recombine signals. It can't function as any kind of gate, not even a wire. What I'm trying to lead up to is a question: what physically computable numbers, if any, cannot be computed by this model? If this model proves sufficient to compute any physically computable number, then may we simply dispense with A-machines as an intellectual curiosity? Further, by performing work on the representation of a signal, may we not likewise dispense with the VNA too? This is why I'm at pains to describe the non-informational (which needs a word, and exformal seems more apt to me than "representational" or anything else I can think of) elements of the model above. The parts that transform signals and empirical context into bits. I'm suggesting that this work of representation itself is a computational process, and a powerful one. And this is why I pointed out the Happel patents below, which I feel illustrate a general approach to doing this kind of work.
- Let's say, for example, you have a sensor that will sense whether or not a TM's head is in the left or the right half of the tape. Or on an odd or even square - anything you like that the machine itself can't tell from looking at the square under its own head. When the C-machine itself is the subject of the sensor and uses this signal to determine its own behavior, it obviously can't be simulated by an A-machine.
- Since an A-machine can simulate all this all by itself (modulo the open quantization issue, if that's involved here), it's not obvious to me.
- Of course the quantization/representation issue is the point here.
- So the question is, has anyone proven that there is a physically realizable environment in which to place an A-machine (which, by communicating with an environment, becomes a C-machine), which makes that machine more powerful than anything that could be simulated on the A-machine in the first place? And the answer is clearly "no", although there are speculations about the computational power of a quantum computer. And if we prove that quantum computers are in fact more powerful, it's unclear why one would then bother with the C-machine; it's the quantum computer that would have the higher level of power, not the C-machine, which come to think of it, would be our IO processor for the quantum computer. :-) -- Doug
- I agree a C-machine could function this way; quantization is its bag. But I disagree that a C-machine is necessarily all of an A-machine in a physical environment; Turing doesn't define it this way. I dare say a machine that quantizes any single bit onto a finite tape should be regarded as a different class of machine to an A-machine. It can neither simulate nor be simulated by an A-machine.
- I should mention that, although some people firmly believe that humans are more powerful systems than UTMs, which if true might boost the power of a C-machine which communicated to an environment consisting of a human, this has not been established, in two very clear ways: first, it hasn't been proven that an A-machine cannot simulate human thinking, and secondly, human thinking is inconsistent -- it is commonplace for people to believe things that are false and/or contradictory to other beliefs or even to themselves (that was e.g. Penrose's mistake).
- Humans are FuRphys. Actually I've wanted to say that for a long time ;-) But as argued above a flower can be a more powerful system than a UTM, depending on your intent. Flowers and UTMs are incommensurable.
- Inconsistent systems are traditionally regarded as less powerful than systems which are TuringEquivalent, and indeed it's hard to see how to call a machine "more powerful" if it gives wrong answers (although nonmonotonic logic such as JohnMcCarthy works on has some ideas loosely in that direction, modulo a hugely-needed paraphrase). -- Doug
- Is a flower inconsistent?
- The possibility that they are irrelevant is completely speculative and has never been demonstrated.
- Can you think of any way to generalize the A-Machine results to C-Machine? If so, you're doing better than a lot of people smarter than you and I have been able to do in the last 70 years. I think that's how the argument went ;-)
- No no no. The point is that you're trying to have your cake and eat it, too. You are making the very strong (and completely speculative and unsupported) claim that "his more famous results on Computability are irrelevant to what physically realizable machines can and cannot compute." You don't know that they are irrelevant! They may or may not be, but you stated it as an absolute truth. Then you turn around and say things like "it simply says those proofs don't apply. The burden of proof remains with you." -- which is the kind of point I'm trying to make. The proofs haven't been demonstrated to apply...nor have they been demonstrated to not apply. If you do in fact believe your own sentence that I just quoted, then logically you should edit all of your other claims to match that, avoiding claiming that the unproven is truth. Specifically, above you should at most say "his more famous results on Computability MIGHT be irrelevant to what physically realizable machines can and cannot compute", and then we could have a fair and sane discussion beginning from that.
- You're right; that claim was too strong. I thought it best to just delete it.
- The issue about C- vs A- machines is, to my mind, merely a question about closed versus open systems, so this sort of speculation is sort of like the frequent claims that open systems break the laws of thermodynamics (which they do not).
- Actually if you'll read the original 1936 OnComputableNumbers you'll see Turing is quite explicit; his results do not treat C- machines.
- Yeah, but I'm saying that it is a huge speculative leap to read anything into that. Just because he didn't make a claim on the subject, is no reason to act as if that proves that it's a whole new ballgame.
- It proves nothing of the sort. It simply says those proofs don't apply. The burden of proof remains with you. Until you can heft it, you have no business saying things like "FPGAs can be simulated by a TuringMachine", etc. That is speculation.
- To compare his construction with thermodynamics seems a RedHerring; thermodynamic systems are obviously physically realizable. If you're arguing that a closed thermodynamic system is computationally equivalent to an A-machine I believe you're carrying a heavy burden of proof.''
- Not at all. I'm not saying that. I'm just saying that the question of open versus closed systems is identical in both cases, not that the systems (computational, thermodynamic) that are open or closed are identical.
- So let me guess again. Perhaps you are trying to say that the metaphor of open/closed that applies to empirically testable thermodynamic systems also applies to A/C machines, despite that fact that no results on A-Machines are empirically testable because A-Machines don't actually exist? Or maybe you're saying that thermodynamically closed systems constitute InfiniteStateMachines and thereby can be compared with A-Machines? Or maybe you're saying that physical theories and formal systems theorems are somehow identical? Or some other category error? Please do feel free to jump in and let me know what you're actually trying to say here ...
- To be very explicit: I think that you commit the cardinal sin of thinking that, if A is not proven, then not-A is proven, which obviously is false.
- To be very explicit: I think that, if A is not proven, then we should not assume A. You seem to think that if A is not proven, we should assume A, which obviously is false.
So what computability limits are there on C-Machines?
There are none known beyond the information theoretic limits of physical scale and energetics. Combinatorial complexity represents the dominant scale limitation. If you take the suggestion on GeneralHaltingProblemProblemProblem seriously (There are two exformal operations necessary to dispense with combinatorial complexity. The first is that the bits represented by your computer must represent the most significant empirical distinctions on the signal under interpretation. The second is that the remaining state required for your computation is represented by the source of signal itself, not by your computer.) then there may be a way to go about such operations. SaulAmarel's CannibalsAndMissionaries provides an example, but no general approach to such reformulation has been published.
For the record, Pete wrote the above, not me; the way the page is laid out currently, it looked as if I'd written the whole thing, but no. -- DougMerritt
I did do some cutting out words and into sentences pasting them. Please feel free to ReFactor, Doug!
You miss the point. The primary paragraphs above were authored by you, the primary paragraphs below were authored by me, that's all, and I wouldn't want someone to think that your claims were made by me, since I disagree with them. Thus my disclaimer.
I'm interested in working our dialog into a consensus
- Then please stop using neologisms like "exformal". You might as well say "frib frab jingle jangle", for all it communicates.
What are the physical limits?
There are a lot of fairly old results in general relativity in this direction; the information content in a boundary is what is considered to be responsible for Unruh-Hawking radiation of accellerated objects, a special case of which is Hawking's celebrated result about radiation from the "surface" of black holes. A related old result is that black holes contain information only in proportion to their surface area.
Even those old results are not absolutely proven.
Newer topics in this direction: 't Hooft-Susskind holographic hypothesis from circa 1991, and Bousso's improvement on it circa 1999. There was a Scientific American article that talked about this, but I don't remember when.
My buddy John Baez discusses the topic briefly in http://math.ucr.edu/home/baez/week57.html
The bottom line is that many people find that Statistical Mechanics makes it, let's say, extremely reasonable to assume that the total maximum information in a volume of space is proportional to the surface area of that volume, but that it's only reasonable and workable thus far, not absolutely proven.
BTW when reading about this, note that entropy and information are the same thing; two sides of the same coin. Formally and literally, not metaphorically. -- DougMerritt
Oops! Forgot the important part: on the other hand, it is true that the amount of information concerning a volume of space available to an external observer is limited by and proportional to the surface area of that volume. Let's say hypothetically that a volume of space actually contains an infinite amount of information. An external observer will never be able to ascertain that; they will always observe only a finite amount of information transmitted through the boundary. This is a result of an equivalence relation between an isoclinic boundary and an infinite set of possible elements contained within that are identical under the isoclinic equivalence relation.
So the result that I stated before may or may not be literally true, but it ends up being true for all pragmatic intents and purposes. -- DougMerritt
Can't fractal boundaries encode as much information as you like? There may be energetic impracticalities at sensing it ...
Good question, that goes right to the heart of it. The question is how much fractal detail can be seen from a distance, in essence. If observation is done via analytic functions (static fields, including electrostatic), then you can draw isoclines around the object at greater and greater distances, and the isoclines get smoother and smoother the further away you get, losing more and more detail -- and already have some smoothness (no discontinuities) at any finite distance at all. Well, that could be nitpicked. Let's say at most a finite number of discontinuities, which still implies finite information.
Any given isocline boundary, of any shape whatsoever, can be created by any one of an infinite number of different objects within the boundary. You can visualize this just by staring at the classic isoclines around the MandelbrotSet, or more prosaicly, by visualizing wrapping a highly detailed sculpture in thicker and thicker layers of foam rubber.
A similar problem comes up if observation is done via non-analytic functions, such as dynamic fields with compact support (the ability to have discontinuities over time and space), e.g. physically realistic light as opposed to Newtonian geometric optics. Here similar results follow from things like the fact that a finite observing aperture can only capture finite information -- a basic theorem of Fourier optics. -- DougMerritt
You know, and feel free to move/delete, this idea that entropy and information are equivalent seems bogus. As hinted in the above point, just because there is a combinatorial limit to the number of states in a closed system, doesn't necessarily mean there is a limit to the amount of information that may be interpreted from those states. That must depend on the observer i.e. on some external structure. If its an open system, then the information content may be resolution contrained, but not semantically constrained. Thus, I think, the problem people have reconciling order with 'low information', and randomness with 'high information'. Just a thought :).
- Just to clarify, entropy and information being equivalent is extremely orthodox, universely accepted (you know -- by experts in the field -- not by my mom), and is a mathematical issue, all of which can be easily verified via google -- this wasn't some passing brainstorm. Does that matter? (It should.)
Ah yes, the orthodoxy, my sworn enemies. The channel capacity relates to the number of distinct states, which Shannon called Entropy
http://www.lecb.ncifcrf.gov/~toms/information.is.not.uncertainty.html .
But information is not necessarily equivalent to data since information presumably has a semantic interpretive context i.e. 1 bit can supply an enormous amount of information. In an open system this is highly significant.
Equally my mumblings here may be highly entropic but carry very little information. ---RichardHenderson (for it is he).
- Sure, sure, but this part of what you said, Shannon also said, that's just orthodoxy. But stronger: information is never the same as semantic interpretation, by definition, so it merely confuses the subject to use the word "information" to refer to both. The part of Shannon's work that applied to semantic interpretation was never declassified, for obvious reasons (although he probably didn't make InformationTheory-like breakthroughs on the topic anyway).
- So it's really a terminology issue. Information and entropy are equivalent, and it sounds like you know quite well why, but on the other hand, the semantic knowledge transmitted by a message is not equivalent to either information nor to entropy, and it's unclear what it is equivalent to. It's not a very well understood subject.
Okay. Words are bendy things. I can live with that, though "data" may be a more accurate term. More orthodox too in some circles. Perhaps even more meaningful. I think the difficulties of semantics are to do with cultural barriers and implicit assumptions. It is possible to be quite simple about these things if you do not ascribe ego to the interpreter but simply identity. But I digress....as ever.....the key point is one of separation. Since state exists outside the computational boundary, but accessible by it, then the channel capacity becomes essentially unlimited over a sufficient period. If the channel includes 'program', then the machine itself becomes unconstrained up to the limit of its 'power' i.e. the degree which it can combine elements simultaneously.....which wanders about your discussion above in a way....
Hmm. This seems like the long way round (maybe the long way round has to be exhibited for the short way round to become visible to those of us less smart). So, what about SignalProcessingAsComputation
Regarding information as entropy, here are some concrete examples from computer programming:
- Hairy syntax: syntactic sugar leads to density of information, thus entropy. The more flexible a language becomes, the more likely an aribitrary erroneous statement cannot be differentiated from a correct statement with a divergent meaning.
- Compression: compressing data is the act of increasing entropy (same amount of information in a smaller space), thus the impossibility of losslessly compressing white noise.
Computation As Signal Processing