## How to Program the Many Cores for Inconsistency Robustness

Folks,

You might be interested in a video of my Stanford colloquium at How to Program the Many Cores for Inconsistency Robustness

Click on the link after my name for abstract and slides and click on the camera icon for the video.

Cheers,
Carl

## Comment viewing options

Just sayin'.

### Excellent suggestion!

At the suggestion of Z-Bo, I put it on my homepage.

Thanks!
Carl

### Responses

Is there any response to the points raised by Thomas Lord and John Shutt last time this topic came up in the forum? As far as I can see those threads simply stopped without reply. I'm curious as the line of argument taken is very similar to a question that I wanted to ask. If I take the definition of NDTM "1*" from last time:

state 0:  emit 1, move right, goto EITHER 0 or 1
state 1:  halt

But this time consider how it executes on a modified definition of a NDTM with a fairness guarantee: i.e the machine will make a non-deterministic selection of state each cycle but state 1 will be picked eventually. As far as I can tell this is exactly the computation that you are claiming separates Actors from TM's - could you confirm that the only difference between the two models is the fairness constraint on the transition?

Furthermore I would claim that this NDTM-with-fairness could simulate any program in the Actors model. Could you either confirm that claim, or provide a counter-example that could not be simulated on this machine?

### re NDTM v. actors

Andrew I think you misunderstood my argument back there.

"Fairness" is completely beside the point. Rather:

Suppose that you take an Actor model and give a theorem that itself or in its proof makes use of the Actor model's concept of "eventual message delivery".

In every case, mechanically, I can translate that into a theorem about NDTMs without needing to add any concept of "fairness" to the NDTM model. For every statement about Actor termination conditions, there is an analogous statement about the sets of NDTM conditions achievable in some finite number of steps. Any reasonable, fully traditional formalization of NDTMs and any reasonable, traditional formalization of Actors are equivalent theories. Neither formally tells you more about computation than the other. Each can be seen as a fairly natural model of the other. In my opinion, there is some confusion about foundation of math issues in Clinger's work that is interpreted as proving otherwise.

The actor model may have informal conceptual or notational advantages but sometimes stronger claims seem to be made about it that I don't think hold up.

### Clarification

Yes that sounds as though I've misunderstood. NDTM's are not really in my area so I have missed one of the important details. I had assumed that given a set of possible transitions from a state that the selection was entirely non-deterministic (i.e the same transition could be selected infinitely often if the machine loops through that state). What I was phrasing as "fairness" was simply a guarantee that at some point a different transition would be selected.

Would it be true to say you are using "terminates in a finite number of steps" as that guarantee - and then working backwards to say if the NDTM did terminate in a finite number of steps then it must have taken an alternate transition from that state?

I am somewhat confused as I thought that NDTMs and TMs were equivalent in power. Yet the busy beaver function is a bound for computation length on a TM, but by your description a NDTM could execute the same program used as an example in the Actor model and output an arbitrary sized integer. Does this come down to the definition of "machine that always terminates"?

### re: Clarification

What I was phrasing as "fairness" was simply a guarantee that at some point a different transition would be selected.

Given a traditionally defined non-deterministic turing machine we can trivially speak of the sets of all machine configurations (state, position, and tape contents) achievable after N steps. For machine M and non-negative integer N, call the corresponding set Configs(M, N).

For each M and N, a possibly empty subset of Configs(M, N) is the set Finals(M, N) which are all the configurations in Configs(M,N) in which the machine is in a final state.

Every actor theorem that supposedly can't be achieved for turing machines can be mechanically translated in a fairly natural way back into a theorem about Finals(M,N). Actor models of computation aren't somehow fundamentally "more powerful" than TM models. Claims otherwise just misunderstand how the formalized math of NDTMs works.

It is interesting that you say this:

I am somewhat confused as I thought that NDTMs and TMs were equivalent in power. Yet the busy beaver function is a bound for computation length on a TM, but by your description a NDTM could execute the same program used as an example in the Actor model and output an arbitrary sized integer. Does this come down to the definition of "machine that always terminates"?

What do you mean by "always"? What do you mean by "terminates"?

For a given actors' theorem, my proof is likely to reason about "always" by some kind of induction over global states achievable in discrete steps over time.

For NDTMs, same thing, probably with reference to Finals(M,N).

For the DTM model of the same theorem, same thing again although be aware that so-called halt states in the DTM state machine specification are not going to play the same role as the halt states in the NDTM state machine specification.

The three different models, all of exactly the same thing, are trivially interchangeable for any proofs about the computable. Sometimes one is a more convenient notation or intuition than the other, is all.

### "always" and "terminates"

What do you mean by "always"? What do you mean by "terminates"?

Yes - this is the part that confuses me. If I use the definition of a machine at the top of the thread as an example then it's not clear to me that it always terminates. It is true that every state in Finals(M,N) would be a unique value of N in state 1, and also (by induction) that every natural number would occur in a configuration in Finals. But there is also one infinite trace that always selects state zero. So the machine given would generate an unbounded integer, but with the possibility of non-termination.

Would this machine (or some version of it as a NDTM) give rise to the claim that it always terminates yet can generate an integer of unbounded size? Or if the problem is with the way that I'm using "always terminates" then what kind of definition would normally be used in this context?

### re: "always" and "terminates"

But there is also one infinite trace that always selects state zero. So the machine given would generate an unbounded integer, but with the possibility of non-termination.

It would be non-standard to introduce an axiom of transfinite induction in an NDTM formalism so I can't tell what you mean by "is also one infinite trace taht always selects state zero".

A related problem with the Actors model is that the axiom of finite time message delivery is non-constructive.

### Makes sense

Ok, it makes sense now: the question can't be phrased over NDTMs because there is no such thing as an infinite trace. NDTMs are only defined over finite numbers of sets / finite sized set of configurations. I remember somebody mentioning this in the last thread although I didn't realise the significance.

### Nondeterministic Turing Machine

You can always say that you are "adding" X to a mathematical model. However, it is often not clear what this means. What you need to do is to define a new mathematical model and investigate its properties. Lots of different kinds of "fairness" (e.g. "angelic" and "demonic") have been discussed in the literature without being of much help.

In general, nondeterministic state machine models (e.g. Nondeterministic Turing Machines) are incompatible with concurrency. There is more information available in the video of my colloquium at How to Program the Many Cores for Inconsistency Robustness. Rather than sticking with NDTM, you would be better off spending your time studying state of the art concurrency theory and practice.

### Slides are available for the video

Slides for the video How to Program the Many Cores for Inconsistency Robustness are available here here.

### slideshare is a pain

I'm sorry to bother you with such trivialities, but slideshare is definitely not a comfortable way to browse documents. Is a pdf export available somewhere?