Lambda the Ultimate

It is for this reason that I feel the obsession with ultra-pure functional languages is a misguided path.

Perhaps I'm misreading your comment, but if you take a look at the papers accepted to ICFP'05, for example, you'll notice that there are several papers that (basically) deal with the integration of imperative (or effectful) and functional programming. The FP research community is exceptionally well aware of the issues.

Actually there is nothing that says that a TM can't analyze another TM for termination. Church-turing only says that there are cases that are undecidable. As far as I know it might be posible that the undecidable cases could be as rare as to not show up in practice. (for some sufficiently advanced analysis process)

There is a diffrence between "a TM can analyze another TM for termination" and "a TM can analyze all other TM for termination".

I'm not sure we understand each other so let me refrase me:

For some TM1 there exists some TM2 that can take TM1 as input and output True if TM2 will terminate for all posible input, and False if TM1 might suspend.

As you can pick TM2 based on TM1, TM2 can ignore its input and just output a corresponding boolean. Do you really mean: "There exists TMTrue that (always) outputs True, and there exists TMFalse that (always) outputs False"?

uhm, yeah know that you mention it of course it is. And yes that seems to be what I meant in a way. My point on the other hand was more like that the halting problem need not be a problem in all cases.

Felicia has already said that what you said is what she meant, but I think it might have been appropriate to mean something else: Namely, that there exists a machine T such that, if T halts with input a given machine S, then it correctly returns an answer to whether or not S halts on all inputs.

Of course this is itself trivial—T could just be taken to loop on any input—and any modification I can think of (like requiring it to halt on some input) could still be easily met; but I think it's a bit more in the spirit that one might want.

I was being very sloppy in my wording because I didn't want to spell everything out. I was really making the much more powerful claim that in principle, I believe that brains can analyze the termination of TMs for which no UTM can decide an outcome. How's that for controversy!

Show me a TM A and your conclusive analysis of its termination and I'll show you a TM B that decides whether TM A terminates or not.

I have no argument with that. However, what might be more difficult for you to do is to show me a TM C that computes TM B given TM A. ;> I argue that C is your brain, and that C is fundamentally different from B and A.

However, it should be easy to implement a TM C that computes such a TM B given an arbitrary TM A and the result of a conclusive analysis of the termination of the TM A. ;-)

I doubt that my brain can determine whether any given TM terminates or not.

Give yourself some credit! ;> The problem with the TM architecture is that it is a Harvard architecture. It segregates code and data, and forces code to be immutable. In fact, this is why the Halting Problem is undecidable for TMs. Given a TM X that can decide haltability for all TMs of size <= N, it is easy to contrive a TM which X cannot analyze. But that's just because X is too brittle. So we have to create a new TM Y, which can analyze the domain of X plus our new TM.

Now, what if X could somehow morph into Y? What if we invented a new architecture which freely mixes code and data? What if we put the TM's state transition table on the tape itself?! Now we would have a different beast entirely. I claim that such a machine would be strictly more powerful than TMs, because I claim that such a machine would be able to solve the Halting Problem! Furthermore, I claim that your brain is a finite instance of such a device.

Unfortunately, I don't have anything by means of a proof. But perhaps my wild hand-waving will be fairly persuasive. ;>

Have you heard of a thing called Lambda Calculus? deviced by Alonzo Church as in the Church-Turing thesis. In lambda calculus there exists absolutly no distinction between code and data. And it is proven to be exactly equivalent to a turing machine.

At the very least, the lambda operator is always "code". I submit that this corresponds to the core functionality of the Turing machine which is represented by the state transition table. Furthermore, that implies a corollary to my claim that lambda calculus is hamstrung by undecidability because the lambda operator is not powerful enough.

Well the fysical laws of our universe might be seen as imutable code in any system. So your brain isn't any better off.

Your brain is relatively hard-wired as well. Your neurons don't really change that much after a certain point. The key is that the TM state machine isn't directly equivalent to "code". You can encode "code" as TM tape data as well. That's what a universal TM does.

I disagree. I claim that the state table *is* directly equivalent to "code", but that you can *also* encode "code" on the tape. Apparently, I am claiming that this ability to put code on the tape is not sufficient; and that changing the state table dynamically (especially by increasing its size) confers a new ability upon TMs that allow them to solve a greater range of problems. Just making a wild guess here, but perhaps the onerous task of "swapping code to tape", so to speak, during the course of solving a "hard" problem like the Halting Problem causes the machine's behavior to diverge more quickly than it needs to, and increasing the size of the state table reigns in this runaway growth.

Or perhaps it's fatally flawed by the existance of things like universal turing machines. Lisp, to give an example, doesn't have the limitations you complain about - yet you can't solve the Halting Problem for either Lisp or TMs in Lisp.

The problem with a UTM is twofold: one, you need to provide the definition of a TM as input, and two, you can only emulate a TM with it. And, as I pointed out before, a TM already has a limited computational repertoire, so emulating it with another TM doesn't get you anywhere. The fact that you have to provide a TM definition tells you something about UTMs: they are just shells. Big deal. A TM is already a pretty simple device, so emulating one in one isn't that impressive a feat. I think it is easy to assume that "universal" in "universal Turing machine" means more than it does. What would be more interesting is a TM that emulates the dynamic TM that I described. It seems that it ought to be possible, but I haven't thought about it hard enough to decide either way.

Take a UTM, add a couple of special states intended to extend or modify the state table of the TM it's emulating. No big deal.

...and tell me how it works out for you. ;> The devil is in the details, as always.

It'll work, it'll still be running on a TM, therefore it'll be no more powerful than a TM. It turns out that "copy this to that pre-marked location" and variants thereof are all doable on TMs, so building the modified UTM isn't that hard if you've been playing with them - I haven't for a year or so, and thus I'm not about to provide you with the actual machine, but I know it's possible in much the same way I know I could write a TM emulator in something like Haskell.

If you execute a VM on a Turing Machine, its instructions are just data which can be modified (as is indeed done with many real VMs).

Undecidability is an artefact of the infinite memory available to a Turing Machine. It can be proven that the halting status of a Turing Machine with bounded memory can always be determined (albeit with a ridiculous amount of calculation, since each combination of memory states may possibly have to be examined).

Since all known Turing Machines have bounded memory, we can, in principle, determine whether each of them will halt or not.

I believe that brains can analyze the termination of TMs for which no UTM can decide an outcome.

How do you plan to decide whether a particular brain has correctly analyzed a TM? Or is your belief religious in nature?

I would ask for a proof, of course. How do you decide if a TM has correctly analyzed another TM?

At the least, we'd expect a hint as to how interactivity could dismantle the halting problem proof. I can't even see how interactivity enters the picture.

I never meant to imply that interactivity has anything to do with the Halting Problem. My apologies if I somehow led you to that conclusion. My claim about the Halting Problem stems from self-modifiability, which is quite distinct from interactivity.

Self-modifiability doesn't buy you any computational advantage.

You seem to assert that a "modifiable" turing machine (one whose definition/programming can be changed on the fly) is more powerful than a classical TM. You equate TMs with Harvard architectures, whereas modern computers are Princeton (von Neumann) architectures.

Someone else points out the existence of UTMs, which treat the "programming" of a classical TM as data--essentially they are analogous to von Neumann architectures.

You seem to suggest that although the machine the UTM is emulating may be modified by the TM's action, the UTM itself is fixed. What if someone uses a UTM to emulate another UTM? What if this is carried out ad naseum?

I don't mean to be rude... but you're making claims that have long been proven false. You might go re-read the relevant literature on the topic.

I don't mean to be rude... but you're making claims that have long been proven false. You might go re-read the relevant literature on the topic.

I'd love to see literature which refutes the points I'm making. But I suspect there is a subtlety that is being missed.

Someone else points out the existence of UTMs, which treat the "programming" of a classical TM as data--essentially they are analogous to von Neumann architectures.

No. A UTM doesn't get you any further than a TM. In particular, the UTM does not modify the simulated state table of the simulated TM. If it did, then by definition it wouldn't be simulating a TM.

You seem to suggest that although the machine the UTM is emulating may be modified by the TM's action, the UTM itself is fixed. What if someone uses a UTM to emulate another UTM? What if this is carried out ad naseum?

That would be great, except you still don't escape the Halting Problem. Why? For a few reasons. One, emulating UTMs is the wrong tack. A UTM isn't any more powerful than a TM. Two, the level of nesting is always finite, which is exactly the reason for the undecidability of the Halting Problem for TMs. "If we could only extend our HP TM to analyze *that* TM!" Three, the deeper the nesting, the larger the input tape. At some point, solving the problem would reduce to specifying the correct enormously large input, in which case the TM itself is but a silly formality.

Now, perhaps what you are trying to say is that a TM could emulate a DTM (as described here). However, I've already conceded that I don't know whether this would be a successful venture, and why I suspect that it would not. That is, I don't see a reason off-hand why a TM could not emulate a DTM, but I entertain the possibility that *even if it could, it might not halt for all inputs that a true DTM would halt on*. But looking at my DTM spec, or trying to design one yourself, I think you will begin to see that it is an interestingly different beast worthy of at least a pause for consideration.

I'd like to try to clarify something. In another comment, you state "that such a machine would be able to solve the Halting Problem! Furthermore, I claim that your brain is a finite instance of such a device." Now, we already know that humans can't solve the halting problem (see Can humans solve the halting problem?)

However, the substance of your argument in fact seems to be claiming something quite different: that a key respect in which brains (human ones, at least) are different from TMs in that they are able to generate fresh proofs, in some cases, given arbitrary problems such as particular instances of the halting problem.

So, I'll assume for the moment that your claim about brains being "able to solve the Halting Problem" was not meant in the usual general sense. You are claiming that the human ability to generate original proofs distinguishes them from TMs (by "original", I mean "not generated by a known algorithm").

While this is intuitively appealing, no valid argument has been proposed to support this. The idea that TMs (and their lambda-calculus-based cousins) cannot modify their own state has been pointed out as false. Is there any remaining (scientific) basis for this belief about brains vs. TMs?

If this were settled, then it would also settle the debates regarding the question whether an AI would ever "really" think. I of course think that it would, because I strictly believe in the identity of indiscernibles and not leading LtU offtopic.

Well, it *hasn't* been proven that humans cannot solve the halting problem; but of course, it would be foolish to claim that any living ones currently can (talk about covering my bases!). Nor did I claim that humans could (or mean to imply that they could). Rather, I claimed that brains are based on an architecture which has the capability of solving the Halting Problem. Let us call this architecture the DTM (Dynamic Turing Machine).

Now, it is *not* false that TMs cannot modify their own state tables. This is true by definition. A TM could modify the state table of a *simulated* TM, but that is different from saying that a TM == a DTM. Note that a UTM could not do this because UTMs only emulate TMs. So the question is, would a DTM simulated on a TM be as powerful as a real DTM? If the answer is yes, then it follows that DTM == TM, and my claim falls on its face. If, however, a DTM turns out to be able to solve a strictly greater set of problems than a TM, then we will have the curious fact that emulating code on tape is not as powerful as making that code an intrinsic part of the machine.

This probably sounds like a fantastic claim to make, so why do I believe it might be true? If we were to design the DTM to be as similar to the TM as possible, its design might look something like so:

1. We move from a 1D tape to a 1.5D tape. By that I mean we extrude a horizontal tape in the +y direction only. Since a finite set of tapes does not increase the computational power of a TM, and since I promise to only use a finite but unbounded area of the tape at any given time, I suspect there will be no objection?
2. We index the tape. Each vertical strip of the tape has an "address", and the read/write head starts at 0.
3. We introduce the "instruction set", which is a set of 4 symbols corresponding to "left", "right", "up", and "down". We map them to the integers 0-3.
4. We introduce the "instruction pointer" (whose address we call IP), which is like a read-only version of the read-write head, with a few special properties:
   1. It can move to any address instantaneously.
   2. It can read an unbounded number of symbols vertically instantaneously. Now, to prevent "cheating", we will say that the instruction pointer always reads symbols from the "bottom" of the tape vertically until it reaches the first blank cell after having read at least 1 + log_N 4 cells.
   3. It starts at address 0.
5. The set of symbols is mapped to the shortest contiguous sequence of the naturals starting at 0. Multi-symbol strings are translated to addresses by the usual base-n notation. The number of symbols is called N.
6. The state transitions occur as follows:
   1. The symbol under the read/write head is inspected. Let us call its address-value A
   2. The instruction pointer moves to address IP + A.
   3. It reads the vertical symbol-string at that address. This value is the encoded state transition instruction, which is as follows:
      1. The first cell is the write-symbol, which the read/write head writes to the cell it is over.
      2. The next log_N 4 cells are the "opcode", which correspond to "L", "R", "U", "D". If the opcode decodes to any other value, or a "D" instruction is issued when the read/write head is at the base of the tape region, it is considered a halt instruction. The read-write head moves in the direction specified by the opcode.
      3. The rest of the cells are the new state S. If S is empty, the machine halts.
   4. It moves to address S * N.

Some of the seemingly-unemulatable-by-TM properties you've listed are present in the "random access machine" computational model. TMs can emulate random access machines.

I can't find any good references on random access machines. Do you happen to know of any?

If, however, a DTM turns out to be able to solve a strictly greater set of problems than a TM, then we will have the curious fact that emulating code on tape is not as powerful as making that code an intrinsic part of the machine.

Which seems like enough to refute your argument, at least intuitively. What causes you to suspect that such a situation might be possible?

All your designing of tape-based machines seems rather quaint to me. The lambda calculus has a fundamental philosophical lesson to teach here: everything that ordinary Turing machines do can be achieved simply with abstraction via names, binding names to values, and dereference of names. If you want to claim that your DTM improves fundamentally on what TMs and LC can do, then rather than throwing out a list of v2.0 features for your tape machine to have, it'd be much more convincing to describe an augmented lambda calculus (or similar model which doesn't appeal to arbitrary physical analogies) which exhibits this new computational property that allegedly cannot be successfully simulated.

That would force you to deal with the logical properties of this new computational model, rather than hiding at one remove behind a list of "hardware" features which you're speculating, with no evidence, have a profound impact on the computational properties of the machine.

Rather, I claimed that brains are based on an architecture which has the capability of solving the Halting Problem. Let us call this architecture the DTM (Dynamic Turing Machine).

IOW, your conjecture is that self-modifying TMs are not only equivalent to human brains, they also have the capability of solving the halting problem in general, somehow overcoming the logical contradictions this entails (and incidentally resolving a large number of unsolved problems in mathematics). I think at this point, all I can say is: I bet you're wrong.

That is, the reason brains can do such magnificent things is because they turn themselves into different TMs on the fly!

Interestingly, the reason functional programs can do such magnificent things is because they turn themselves into different functional programs on the fly! That's exactly what happens each time you apply a function like (lambda (x) (lambda (y) (+ x y))) to a value: a new function is created, essentially turning the running program into a new program, which embodies some additional state (a particular value for x). This is just a minor example to illustrate one of the ways in which functional programs interact with state.

Extrapolating from this, one gets to monads, which package this capability into a standardized, reusable form which augment themselves each time they are invoked. "The reason monads can do such magnificent things..."

The parent post demonstrates a common misconception about state in functional programs, and reaches the wrong conclusions as a result. Mutable state is an optimization in which the time dimension is folded so that subsequent values overwrite previous values. Correctly preserving the history of previous values, as pure functional models do, provides a more faithful model of any system involving a time-like dimension, including the real world.

This is why things like accounting systems and transactional file systems are purely functional at the logical level.

The claim that "Brains are the ultimate stateful devices" is certainly not at odds with a functional model. One could just as accurately say that "functions and/or monads are the ultimate stateful devices". The implication that "functional" and "stateful" are somehow at odds betrays a misunderstanding of the relationship between the functional model and state. I highly recommend working through the at least the first three chapters of SICP as a partial antidote to this.

MONAD THE ULTIMATE

Yes, thank's for that input Marcin. ;-)

I don't think the statement was intended to lift monads yet another step on their stairway to heaven. On the contrary, one way of getting 'statefull' computations into a functional program is to pass around (curried) functions, which by all means can be thought of as computations which carry around a state (for example, the argument they were curried with, or some invariants which hold on the function passed around).

Question then becomes, are we then still talking about 'state' in the traditional sense (whatever that is) (?), or about something completely different? And, can the traditional notion of statefull computation be modeled by passing around (curried) functions?

Lambda the ultimate imperative (ftp://publications.ai.mit.edu/ai-publications/0-499/AIM-353.ps). It's top of the list of papers. It would probably be relevant for anyone who hasn't read it and is trying to seriously follow this line of discussion (of which, I must confess that I am scoring 0/2).

And, can the traditional notion of statefull computation be modeled by passing around (curried) functions?

Sure. The use of monads in a pure functional language like Haskell provides an existence proof of this. But to understand the principle, we don't have to go that far. SICP introduces the underlying concept in What Is Meant by Data? (See Exercise 2.4 in particular.)

But what I believe is that the TM that a brain is when it starts to analyze a program is not necessarily the same TM that it is when it decides that it doesn't terminate.

This is well-trodden ground. You should read "Godel, Escher, Bach" (particularly, the Contracrostipunctus dialogue, if I remember correctly) for why this doesn't help. Basically, in order for a machine to change itself there needs to be some process doing the changing, and unless you can prove that this process is more powerful than a Turing Machine, then your whole system, while elaborate, still has the same problems with incompleteness and the Halting Problem. To put it another way: the machine (program) you pass it to analyse for termination includes not only the beginning machine (start state) but also the mechanism by which the machine is changed, which is after all part of the same machine.

I did read that a long time ago (but I should probably read it again). Anyway, the process doing the changing would be exactly the environment in which the machine runs. That is, the inputs during (or between?) the computation would change the way the computation proceeds (because it would change the rules of procedure themselves).

Are you so sure, human, that there is no Turing Machine beyond your power to analyze for termination?

I'm not sure. But it seems to me that given enough time and resources (which may well be beyond human, solar, galactic, or even universal lifetimes), human minds would be able to recognize the patterns that lead to termination or divergence without executing the entire TM. It's not so much that I believe in the power of any instance of a human brain, but rather that I believe in the plasticity of its computational model. What brains appear to be able to do is add on layers of abstraction at will, reducing complex problems to ever simpler ones. When brains fail, it most often appears to be due to a lack of computational resources, and not a failure in principle.

Check out www.aemea.org. I provide a mathematical proof that the Church-Turing thesis is false. I do this by providing a solution for solving the Turing Immortality Problem for any given Turing machine.

Michael Fiske

I think this is interesting work. It appears to be a new class of computation, but it doesn't disprove the Church-Turing thesis because the machine cannot be constructed or simulated with a finite amount of labor.

From the paper:

The DRM has an unbounded number of registers labelled R0, R1, R2, . . . each of which contains a natural number.

From the Church-Turing thesis:

... fulfilling the requirement of finite labor at each step and yet was provably capable of carrying out computations that cannot be carried out by any Turing machine.

So moving data between an unbounded number of registers would disqualify the machine as requiring finite labor.

A Turing machine has an unbounded tape. I haven't looked at the paper much, but skimming the section on the DRM, it doesn't appear to have any instructions that touch more than finitely many registers in finite time, so this isn't much different than the Turing machine's tape. In fact, at first glance I don't see why this new machine couldn't be simulated by a Turing machine... I suppose I'll have to read more.

For any computation of the dynamic register machine, as long as the program terminates, it only uses a finite number of registers. This is the same assumption that Sturgis and Shepherdson make in their register machine paper. This is analogous to the Turing tape being unbounded but for a non-halting computation, it visits a bounded number of tape squares.

Can you explain what about your dynamic register machine would prevent its implementation in, e.g. newlisp?

Also, this theorem,

THEOREM 4.16 If machine (Q, A, η) has an immortal configuration, then it has an immortal periodic point.

seems to contradict the existence of counterxamples such as the one constructed in this paper. Do you know why it doesn't?

You have a number of interesting questions so I will address one per reply. First, let's take a step back. The purpose of a dynamic register machine was to capture in the simplest math formalism the notion that a program should be able to change while it is executing. This has advantages when using machine learning methods in the design of a program.

Yes, it can be implemented in newLISP but will only execute up to the memory bounds of the machines that are executing newLISP. If there were a way to implement newLISP so that the length of a list is unbounded, then it would entirely support the formalism. [I will follow up on this with Lutz Mueller. See www.newlisp.org]

In fact, I wrote a newLISP dynamic register machine that executes the 1,590 line program shown in section 11. I have tested the code on small Turing machines, but have been unable to do so on large Turing machines as I do not have adequate computing resources.

So this brings up an interesting practical question. Can an interpreted program whose length can change while it is executing be more powerful than a compiled program whose executable code stays fixed throughout the computation? I think the answer is yes and what I just mentioned along with sections 0 to 11 explains why.

By the way, Jef Raskin, famous Apple engineer -- http://en.wikipedia.org/wiki/Jef_Raskin -- knew intuitively that there was something missing in theoretical computer science that was not capturing practical computing. He has an essay on the web where he mentions this, but I can not find it. Otherwise, I would cite the essay or commentary in my references.

If there were a way to implement newLISP so that the length of a list is unbounded, then it would entirely support the formalism.

But you don't actually need infinite lists at any point, right? You just need arbitrarily large finite lists? I'm asking because it's well known that lisp can be emulated/encoded in lambda calculus and lambda calculus can be implemented by a Turing machine. So using these emulators, wouldn't your 1590 line program provide a way to solve the Turing immortality problem on a Turing machine - a contradiction?

In regard to the paper:

On the presence of periodic configurations in Turing machines and in counter machines by
Vincent Blonde, Julien Cassaigne, and Codrin Nichitiu

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1435

it does not appear to contradict my work. I took a quick look at the first page and their configuration space is a different topological space then mine.

I understand you have a special topology, but your theorem 4.16 seems to me to be saying that there is some extended configuration for every immortal Turing machine that puts it into a loop (up to equivalence). That would seem to contradict the construction in the paper I referenced that demonstrates a Turing machine that continues from any configuration without halting or looping.

Edit: In other words, your statement of theorem 4.16 doesn't seem to involve your topology much (only its proof does).

My configuration space is a different topological space.

Instead of speaking in generalities, can you send me the explicit Turing machine, what you are calling the counterexample, in terms of a table similar to what I have in examples in Section 3?

I will go through how the methods in sections 7 and 8 work for this particular machine but I probably won't be able to get to this until the weekend.

If the explicit Turing machine is too big to post, please email to mike@aemea.org

My configuration space is a different topological space.

Yes, but points in your space correspond to ordinary (infinite tape) configurations. I don't remember (or see) where you defined 'immortal period point' at the moment, but I thought that was supposed to mean that such a tape configuration that will, upon some finite number of machine steps, return to an equivalent configuration. Is that correct?

Regarding your request for an explicit Turing machine, I'll see what I can do. I wouldn't mind understanding the counterexample a little better so I may send you something.

I am glad that you are asking these questions. The work has been submitted for peer review. Also, there are two different perspectives, math and computer science. Actually, the topology does matter because that determines what the points look like. In order to talk about periodicity, you need to have the topology or metric well-defined. Another point to consider is that the Turing machine in Section 2 that I define is "hyperbolic" in the sense that the rewrite and the left / right tape head move occur as a part of the same Turing instruction.

The "hyperbolic" Turing machine can carry out any computation as the machine defined in the paper -- and any halting machine with respect to their formalism maps to a halting machine in section 2 formalism -- you referenced. I can provide details for this. It is
straightforward so I did not include it in the sections. I figured that it was probably already well-known by the theoretical computer science community.

Assuming the paper's math is correct, their machine that contains an immortal configuration but no periodic configurations will produce a periodic point with respect to the Section 2 "hyperbolic" machine. This may be the answer to your question but I can not determine this unless I can see a state / symbol table that completely specifies their counterexample.

Also, did you notice that the paper was sloppy on how they defined their configuration space? Q x {T: T: Z ---> A} is their definition but their points in their analysis are not points in this space because they also include the tape head. See my definition in section 2, where there is an additional coordinate that accounts for the tape head location.

My configurations are defined in 2.3. They are of the form (q, k, T) where T: Z --> A
where A is the alphabet, but the Phi map in 2.11 creates an equivalence relationship so that two distinct configurations may represent the same point.

Right, I think I understand this part. And I think understand that you want to associate these (pre-equivalence) configurations with a rectangular subset of the 2D plane (though, see my comment [*] below). But where do you define "immortal periodic point"? Does that not mean what I think it does?

Also, this isn't the best forum to use for back and forths such as this, so I'll send subsequent follow-ups to your email address above.

[*] You don't seem to address that the standard map from infinite digit strings to real numbers isn't an injection. For example, the real number 2.5, in decimal, has digit strings 2.5 and 2.4999999... Thus certain points in the plane would seem correspond to 2 or 4 distinct Turing configurations.

and while the SCTT as described is indeed ill-formed, this is hardly a remarkable or notable result. The limitation of Turing machines and the lambda calculus to mathematically-describable functions is well-known.

Well, the paper argues that there are many such misconceptions in CS literature, so it's clearly not as well understood as the authors would like.

But again, unless a human (or an oracle) is interspersed between two nodes in a multi-agent network, it is hard to discern how the existence of a simple communications channel between two processes increases the computational capability of such an aggregation, compared to a single process.

The real world itself strikes me as either a more advanced Turing machine than we have can hope to create, or a true Oracle/O-machine. Continual feedback from sensors seems much more feasible than predicting the progress of the real world from a given fixed state, particularly in circumstances when we don't even know how that state evolves, or the computation itself is intractable.

In particular, I seriously doubt that a network of Persistent Turing Machines (PTMs), interacting among each other but not with the outside world, is any more capable than a single Turing machine.

Theoretically, I agree.

I also seriously doubt that a network of PTMs which is allowed to interact with the outside world (for some value of outside world) is any more powerful than a single PTM doing the same.

Theoretically, I also agree with this. Networks of TMs/PTMs are more of an engineering issue than a theoretical CS issue.

I think I/O with the outside world, and not simply with other TMs/PTMs, is the definitive "advantage" of the PTM model. One could probably argue that PTMs are simply the Church-Turing thesis augmented with the possibility of communicating with O-machines. This is clearly strictly more powerful than TMs alone. I'm not sure that this buys us any useful theoretical enhancements though.

It's certainly well-known that n Turing machines (where n >1, but is finite) is exactly as powerful as a single machine. It's also certainly true that multi-agent models are executed on the same hardware as single-agent models.

This makes it sound like you are "proving" that multi-agent models aren't any more powerful than single-agent models. But the whole point is that the hardware which runs either is not a TM, and is strictly more powerful than a TM with a finite tape of comparable size.

In particular, I seriously doubt that a network of Persistent Turing Machines (PTMs), interacting among each other but not with the outside world, is any more capable than a single Turing machine. I also seriously doubt that a network of PTMs which is allowed to interact with the outside world (for some value of outside world) is any more powerful than a single PTM doing the same.

For an example of the first kind, suppose that one of the PTMs is simulating the local environment in which one of the other PTMs would "ordinarily" find itself. That is, do you accept that the laws of physics can be suitably encoded as a TM? Do you believe the universe is *computable*? If so, then we can take any particular subset, simulate it, and provide it as the input to another PTM. In fact, this is probably one of the things that makes the brain such a useful tool...the fact that it can simulate outcomes instead of experiencing them (which is obviously useful when dealing with lions and tigers and bears, oh my!).

The second claim can be addressed in the same way. A network of PTMs can help simulate the outside world, allowing for the evaluation of strategies that would be more difficult within a single PTM. Now here is where we get into some difficulties. If, in fact, the universe is computable, then we can simulate the entire thing within a single, monstrous TM, thereby eliminating the need for interactivity. The only "inputs" are the initial conditions, and they don't change during the computation. So strictly speaking, this is a critical factor in determining whether PTMs are more powerful than TMs. That is, the Strong CTT is only false *if the universe is somehow non-computable*!

On the other hand, this line of reasoning mostly violates the spirit of the original paper in question, as it seeks to understand machines that are not arbitrarily large, and especially machines that have limited information available to them. These restrictions make interactivity relevant again, since it now makes sense to once again talk about the "outside world". However, the real question, which I sense that many people are driving at, is whether TMs are the right level of abstraction at which to tackle these problems of concurrency and interaction; and I agree with the general sentiment that perhaps it is not.

This makes it sound like you are "proving" that multi-agent models aren't any more powerful than single-agent models. But the whole point is that the hardware which runs either is not a TM, and is strictly more powerful than a TM with a finite tape of comparable size.

The claim that "a machine that can do I/O is more powerful than one which cannot" strikes me as a tautology. And it's one which was well known to Turing himself. At any rate, the definition of "power" is being muddled--in the Church-Turing Thesis (and in the literature on computation theory in general), computational power relates to the ability of different machines to solve different mathematical problems. I/O is intentionally excluded. If one redefines "powerful" to include interactivity (itself a term which is ill-defined), then one hasn't invalidated the CTT; one is simply proposing a new thesis with different premises and ground terms. Why this result, known to Turing 60+ years ago, is worthy of a paper in 2005, I've no idea.

For an example of the first kind, suppose that one of the PTMs is simulating the local environment in which one of the other PTMs would "ordinarily" find itself. That is, do you accept that the laws of physics can be suitably encoded as a TM? Do you believe the universe is *computable*?

I have no idea whether the laws of physics can be encoded as a TM, and neither does anybody else. We still don't know what all of the laws of physics are. Nor do we know whether mass/time/distance are quantized or continuous. Nor do we know a bunch of other things, including whether the universe is computable.

If so, then we can take any particular subset, simulate it, and provide it as the input to another PTM.

In other words, "if we assume the universe is computable, then we can reason about it with a computer?" Yet another tautology.

In fact, this is probably one of the things that makes the brain such a useful tool...the fact that it can simulate outcomes instead of experiencing them (which is obviously useful when dealing with lions and tigers and bears, oh my!).

Which has little to do with the computational power of a human brain, or a PTM, or a bunch of PTMs hooked up together. We still don't know for sure how the human brain relates to Turing machines in computational ability. There is no reason to assume a PTM is a reasonable model for the human brain, if that's what you are suggesting.

The second claim can be addressed in the same way. A network of PTMs can help simulate the outside world, allowing for the evaluation of strategies that would be more difficult within a single PTM.

What do you mean by "more difficult"? If you mean "requires more time", or some other performance claim; that's irrelevant to discussions on computability. If you mean that two (or some finite n) PTMs can solve a problem that one cannot; that would be an astounding result. But nobody has demonstrated such. For classical TMs, the opposite has been proven; and other than systems of PTMs which interact with an external, extra-Turing intelligence (an O-machine, essentially), I have a strong hunch that any system of PTMs you can devise can be turned into an equivalent system of TMs. After all, a PTM looks to me like a 3-tape TM, with two of the tapes artifically constrained--also something exactly as powerful as a 1-tape TM.

Now here is where we get into some difficulties. If, in fact, the universe is computable, then we can simulate the entire thing within a single, monstrous TM, thereby eliminating the need for interactivity. The only "inputs" are the initial conditions, and they don't change during the computation.

Exactamundo!

So strictly speaking, this is a critical factor in determining whether PTMs are more powerful than TMs. That is, the Strong CTT is only false *if the universe is somehow non-computable*!

If the Universe is non-computable, any argument above which assumes that the universe is computable becomes moot. At any rate, if the Universe is "non computable", and there were some ways to harness its properties to enable extra-Turing computation, and that were hooked to a Turing machine--you'd have an O-machine, or something like it.

At any rate, this paper contains nothing new that I could see. Nor does it enlighten us in any significant way about multi-agent systems vs. sequential computation, as you have demonstrated (hopefully to yourself). If I may be a bit bold (and a bit rude), a significant bit of the "interactive computing" literature promulgated by Wegner and his colleagues veers dangerously close to pseudo-science. Not because of deflating the "strong CTT", but because of the underlying suggestion that maybe, jest maybe, interactive systems (which seems to include any multi-agent system, on the questionable grounds that the agents "interact" with each other) are more powerful (in some signficant way) than "classical" systems, becuase the interactive system might someday find an oracle to talk to. At best, such claims are mere speculation--interesting, but not really scientific. At worst, such claims border on FUD.

Wegner and company would do better IMHO to study closed systems, an environment in which they can formulate testable hypotheses and thus produce useful results, than engage in pie-in-the-sky speculation about computers that can talk to the proverbial Flying Spaghetti Monster.

If one redefines "powerful" to include interactivity (itself a term which is ill-defined), then one hasn't invalidated the CTT; one is simply proposing a new thesis with different premises and ground terms. Why this result, known to Turing 60+ years ago, is worthy of a paper in 2005, I've no idea.

I have no idea whether the laws of physics can be encoded as a TM, and neither does anybody else.

We still don't know what all of the laws of physics are.

Nor do we know whether mass/time/distance are quantized or continuous.

After all, a PTM looks to me like a 3-tape TM, with two of the tapes artifically constrained--also something exactly as powerful as a 1-tape TM.

But that's wrong, because, as you stated before, "power X" is defined by the metric: "cardinality of the set of problems that can be solved by X", and since PTMs can solve problems that require "interactivity", as well as all the problems that TMs can solve, then PTMs are strictly more "powerful" than TMs, despite the apparently trivial modification.

But I'm not really a die-hard PTM apologist. I agree that they probably do not offer strong theoretical advantages over TMs. If anything, I think the value in thinking about PTMs is the nature of interactivity (or, as one poster reduced it to: "control"). We have good theoretical results about pure computations, but few if any solid theoretical results about dirty ones.

Do you believe the universe is *computable*?

Quantum mechanics would appear to provide a pretty solid answer to that question: No.

Now, one could posit a deity with the capability of influencing quantum resolution and thus being able to decide whether Schrödinger ended up with a companion or a corpse. One might expect the number of such interferences to be trivial in comparison with the possibilities, and thus indetectable by low-level statistical analysis, leaving the existence (or not) of such a deity outside of the realm of scientific proof.

Furthermore, one could posit some aspect of conscious lifeforms (human beings, say) making them also capable of such influence (perhaps to a lesser extent); under the right circumstances, this would allow "free will" to coexist with a stochastic computational model of the universe. Again, it would be difficult if not impossible to observe such a phenomenon using scientific tools.

I do not believe that LtU is the correct forum for discussing such a concept, so I will not engage here in any debate on the above; indeed, I am pretty well indifferent as to what anyone else might think about it. However, I do highly recommend to those whose immediate reaction is strongly negative that they (re-)read John R. Searle, particularly The Rediscovery of the Mind or The Mystery of Consciousness.

Quantum mechanics would appear to provide a pretty solid answer to that question: No.

Hmm, last I know quantum computing had same annoying problems with irreversible functions and other stuff. It gave me the distinct feeling that at the moment there, well, there isn't anything there yet.

Anyone better informed than me who understands complexities better than me has an explanation of QC?

Quantum mechanics would appear to provide a pretty solid answer to that question: No.

Do you make this statement because of quantum indeterminancy, or some other reason?

Quantum mechanics would appear to provide a pretty solid answer to that question: No.

I'd certainly like to know what makes this answer that solid. I for one cannot see why the universe's Schrödinger Equation couldn't be calculated to any desired precision. Granted, it's a partial differential equation in 10^150 variables, give or take some, but heck, that's nothing compared to the infinite tape of a TM!

Calculating this way will make the damn cat either dead or alive, and Schrödinger looking into the box won't change anything. There's only a "half dead/half living" cat if the system was absolutely symmetric and undisturbed to start with -- which is impossible. (Plus, he should have used a dog anyway...)

But which is it? That's the halting problem with a vengeance.

In other words, you could in principle compute the Schrödinger equation to any desired precision (though whether you could do that fast enough for a prediction is another question) but at the end of that you would still only end up with a probability.

Actually you can't compute it at all. The machine to compute it wouldn't fitt in this universe, I'm talking compexity vise. Current estimates in information physics says that the universe is 10^80 bits, so it realy can't contain an equation with 10^150 variables. It's basicaly the same thing as the halting problem and gödels incompletnes theorem. A problem has a certain minimum and it can't be emulated by any less. thats why you can't generally know what value a function will return with less work than running the function. A speciall case of that being the halting problem.

Seriously, this thread already became quite meta-physical. I believe there is nothing wrong with this (except probably running off the topic of PLT), as the question of notion of computation is a foundational one, and as such lies on the border between science and beliefs. For example, the discussion of the design of human brains assumes we believe that all their powers come from the structure contained in this universe. Imagine a naive programmer (programmatically) duplicating descriptors of the (hardware) processors of his computer in hope to increase the performance. Or Dr. Square duplicating a 2D section of a lovely Sphere only to discover that the copy does not behave like the original at all. Or Mr. Anderson duplicating... You got the idea.

My point is that if we really want to discuss issues like the "real" nature of computation, we have to get a license from Ehud (a philosophy department?).

but at the end of that you would still only end up with a probability.

Actually you don't. You end up with a (quite abstract) function, the amplitude of which has been interpreted by Max Born to be a probability. One of the cats has a _very_ low amplitude there.

To decide whether the cat is alive, you have to know the state of the whole universe, since basically everything depends on everything else to some extent (it's partly a chaotic system). Since you don't know the whole picture, you have to throw some information away, averaging over large swathes of the function. This gives a probability, but is no longer an adequate description of the state of the universe.

To try and get back to the topic: Since solvers for differential equations can be implemented on a TM, and differential equations seem to describe physics accurately, the whole universe is no more powerful than a TM. CTT generalized to an extreme. Currently, there doesn't seem to be any indication to the contrary.

Hm, aren't those only getting approximations (how would they represent things like PI)? The real universe would thus more complicated than what a TM can represent, no?

While pi is a transcendantal number (and the transcendantals are uncountable), there are many useful countably infinite sets which include pi; and many useful ways of representing pi exactly with a finite string--it can be represented as a Taylor series, as a continued fraction, etc.

At any rate, many practical solvers of differential equations use numerical rather than symbolic methods for computation--any term is likely to have some error associated with it. For this reason, exact representation of coefficients, including well-defined constants like pi, is usually not required--a suitable approximation will do. (In engineering applications; measured quantities are assumed to have an error from the start; it's folly to pretend otherwise and represent an imprecise measurement with an exact figure).

One of the longstanding follies of the PLT community (some members, anyway), is the belief among some of us that we can do a better job of number-crunching (usually using symbolic processing techniques) that mathematicians who are experts in this sort of thing (and generally reject symbolic approaches in favor of numeric). I always chuckle when I read somebody from the PL community ridiculing use of things like floating-point, on the grounds that their favorite BigNum implementation is more precise.

Just because computer scientists use math (and are frequently domain experts in the various discrete subfields of math, including theory of computation), doesn't make us domain experts in all of mathematics.

The experience that Java developers had with the numerical community ought to be an instructive lesson to all.

You wrote:

"While pi is a transcendantal number (and the transcendantals are uncountable), there are many useful countably infinite sets which include pi;"

One cannot say that "the transcedentals are uncountable". A number cannot be countable or uncountable, it's a set attribute, not a number's.

While the set of real numbers is uncountable, pi belongs to a set of computable numbers (a subset of reals) which are of course countable.

They get discrete approximations, but to any desired precision. This could even be programmed lazily: evaluate more digits whenever the need arises. Granted, that's expensive on a real computer, but who's counting when the tape is infinite? PI, being an algebraic number, is of course represented as a lazy promise :)

The real universe would thus more complicated than what a TM can represent, no?

Or not. Around the magnitude of Planck's constant, things become discrete, not only charge, energy, momentum, but probably even space and time. If so, there's not even a need for diffeqs.

In the limiting case, yes, I agree with you absolutely: it's nonsense to suppose that distributed systems magically have more computational power than individual Turing machines. N Turing machines communicating are no more powerful that 1 Turing machine.

(I would go a lot further, and say that I even find the claim that "IMs" (to quote Wegner, "interactive machines") are somehow outside of SCCT pretty absurd, not merely 'technically true but irrelevant' as I think I could paraphrase you? It's true that SCCT narrowly, technically, does not apply (you can't "simulate" IO on a machine that doesn't do IO.) But you can view the process of interest as simply a "function extended in time", and simulate that function.* Whereupon all the usual interesting consequences of the SCCT apply, I suspect.)

But there are three caveats:

The first caveat is that once you have parallel composition of processes, you do often need "reactive" models of your processes. Not because the set of computable functions changes. But because parallel composition allows something else to happen in addition to divergance: deadlock. (To speak loosely, we are *narrowing* the set of successfully-terminating processes here, rather than broadening it. This is one way of looking at why we're not really changing SCCT.)

The reactive behaviour of a process is a *very* useful *refinement* of a process' partial-function behaviour. If you don't have it, a process which consumes two apples, then produces two oranges seems the same as a process which eats an apple, produces an orange, rinses and repeats. And the two will deadlock in different (parallel-composed) contexts. Oops.

The second caveat is that parallel composition *really* changes things with non-Turing powerful models of computation, and a lot of programs (and thinking) lives here.

I'll explain the second half of that first: quite a lot of programs carry around with them (if only in their authors' heads) a rough proof of termination.** So at some level, they don't really require the full generality of a TM. Programmers are in the habit of using the limiting results of Turing intuitively to know when they are getting into hot water. If you write something which is suddenly interpreting something that looks like a full-blooded language of directives... you know to watch out for non-termination.

The problem comes with the following (admittedly erroneous) piece of intuition: "I'm composing n boring processes which all, eg, behave like fancy PDAs, I feel safe."

Which brings me to the second point: parallel composition is Alice in Wonderland for some models of computation, notably PDAs. (Arbitrary composition is Alice in Wonderland for DFAs...) Communicating PDAs are Turing powerful (Ramalingam). Communicating DFAs are PDAs, with the right set up of communication.

This is especially bad when people have written in DSLs which are meant to be non-Turing powerful, and then composed the results -- it is made worse by the fact that distributed computation makes it harder to "see" the algorithm which is getting run. This is, for me, where it all starts to be very LtU-relevant again: languages are notations, and implicit models of computation. So what notations make it easy to reason about what happens when things compose in parallel?

The third caveat is quite boring: some processes are intended to run forever. So you need some way of breaking them down. Most of the time, you can break them down into a "functional-reactive" style model. But even this is actually a (primitive) way of treating so-called interactive processes.

What would I conclude out of all this? Just that Wegner is right that we need to pay attention to interactivity (or as I probably prefer, following I think Nielsen et al, "reactivity") --- but he's wrong about the reasons. It's not "breaking out" of the Church-Turing model of computation, it's refining it.

Someday, we'll all be quite relaxed about Turing, and realise that a new model of computation doesn't have to "break the Turing barrier" to be interesting.

(as an aside, it reminds me a bit of of Godel (surprise surprise -- I'm surprised no-one has really trotted out the Turing-Godel correspondence yet)... and how people get a bit too worked up about it. In particular Smullyan has a rather cute statement about why the second incompleteness theorem, whilst wonderful, isn't as bad as it seems: in essence, if a formal system (or salesman...) walked up to you in the street and told you it could assert it's own correctness (or honesty...) would you believe him/her?)

Cheers

*(So the input tape is just a temporally ordered list of inputs, and you expect the output tape to be a temporally ordered list of responses. Sure, some input tapes will be invalid following certain prefixes of output tapes... but you can avoid these if the machine is deterministic. If it's non-deterministic, just allow an "error, rest of tape is garbage" symbol on the output tape.)

**The exceptions tend to be things like interactive programs (which arguably are already reasoned about in an interactive model) and interpreters, which people tend to know about -- at least after the Turing-tarpit crowd get on to it and notice you can use your filelist specification language to write a minesweeper clone that describes the board in morse code...

...it probably means that we need to add I/O and State to our programming languages. One wonders how we got along without these for so long.

It wasn't until the invention of monads that IO become reasonably natural in a purely functional framework, a problem solved only within the last 15 years.

Even then, monads don't make for a "purely functional execution", if such a thing can even be envisioned -- that is, conceptually, monads still rely on run-time side-effects for their execution.

At least, that's how I see monads, with my admittedly limited experience.