Jump to content

Church-Turing thesis is outdated


Recommended Posts

Carl Hewitt, in one of his papers, proved that the Turing Machine is incapable of full-fledged non-deterministic computation. I am too lazy now to look for this paper, I will retell this proof.

Suppose we need to get a random number.
The algorithm for a Turing machine will be as follows:

add 1
go to step 1 or 3 non-deterministically
stop

It may never stop.

For actors, the algorithm is as follows:

Send to yourself 2 messages "stop" and "+1"

The computation is guaranteed to stop.

Edited by altaylar2000
Link to post
Share on other sites
1 minute ago, altaylar2000 said:

I am too lazy now to look for this paper, I will retell this proof.

Can you provide a reference or enough context for a fruitful discussion to take place?

 

Link to post
Share on other sites
  • 1 month later...

After the invention of transistors it goes from something spinning to well logic gates. Personally I would build a computer out of spinning cartridges, but then that would not be revolutionary.

Link to post
Share on other sites
7 hours ago, fredreload said:

After the invention of transistors it goes from something spinning to well logic gates. Personally I would build a computer out of spinning cartridges, but then that would not be revolutionary.

Computers from the era before transistors used vacuum tubes and they did not spin. But maybe you mean things like the mechanics of punch card devices or rotating drums like the ones used in the Atanasoff-Berry Computer? 

"Spinning cartridges" sounds like something from a Jacquard machine. I think you are too late; Jacquard created his machines more than 200 years ago :-)

(Vintage computers are interesting, and how is this related to the topic of Hewitt and actor model?)

Link to post
Share on other sites
Posted (edited)
2 hours ago, uncool said:

Why is one of the computations guaranteed to stop while the other isn't?

I do not know the formal mathematics in enough detail but I am interested in discussing this further. Here is an extract about the first case (1):

Quote

Gordon Plotkin [1976] gave an informal proof as follows:

Now the set of initial segments of execution sequences of a given nondeterministic program P, starting from a given state, will form a tree. The branching points will correspond to the choice points in the program. Since there are always only finitely many alternatives at each choice point, the branching factor of the tree is always finite.41 That is, the tree is finitary. Now König's lemma says that if every branch of a finitary tree is finite, then so is the tree itself. In the present case this means that if every execution sequence of P terminates, then there are only finitely many execution sequences. So if an output set of P is infinite, it must contain a nonterminating computation

Source: https://arxiv.org/pdf/1008.1459.pdf

 

Second case (2):

Quote
From the Actor point of view, sequential computations are a special case of concurrent computations, distinguishable by their event diagrams. The event diagram of a sequential computation has an initial event, and no event activates more than one event. In other words, the activation ordering of a sequential computation is linear; the event diagram is essentially a conventional execution sequence. This means that the finite elements of Diagrams
x_{0}\leq x_{1}\leq x_{2}\leq x_{3}\leq ...
corresponding to the finite initial segments of a sequential execution sequence all have exactly one pending event, excepting the largest, completed element if the computation terminates. One property of the augmented event diagrams domain < Diagrams,   > is that if x≤y and x≠y, then some pending event of x is realized in y. Since in this case each xi has at most one pending event, every pending event in the sequence becomes realized. Hence the sequence
x_{0}\leq x_{1}\leq x_{2}\leq x_{3}\leq ...
has a least upper bound in Diagrams in accord with intuition.

Source: https://en.wikipedia.org/wiki/Denotational_semantics_of_the_Actor_model

As I have limited experience of this so the following (naive) interpretation may be wrong; I am interested in corrections or references:
(1): For the turing machine to be unbounded it has to include an nonterminating computation, hence it may not terminate.
(2): In the actor model there is no option for the actor to skip the stop message once the message is sent. The computation model allows for the stop message to be delayed/postponed for an unbounded time but eventually it will be handled, hence the computation has to terminate at some point. 

The computations (but not evidence) are described in

https://arxiv.org/vc/arxiv/papers/1008/1008.1459v8.pdf

Edited by Ghideon
grammar and clarity
Link to post
Share on other sites

I guess my question is, if the "stop" message can be postponed for an unbounded time, why it couldn't be postponed forever, analogous to the Turing machine algorithm.

Link to post
Share on other sites
Posted (edited)
14 hours ago, uncool said:

I guess my question is, if the "stop" message can be postponed for an unbounded time, why it couldn't be postponed forever, analogous to the Turing machine algorithm.

According to my understanding* the computation in the actor model is mathematically proven to be something like this: a program that goes through the sequence (an)nN will always terminate since the sequence has a last element. The difference is, I guess, a mathematical difference between unbounded and infinite.

In other words, the behaviour of the actor model can be reduced into something like the below pseudocode. It will always terminate at x=n even there is no upper bound for how large n can be:

while x<n:  x=x+1;

The Turing machine on the other hand must contain something like the below, a piece of pseudocode that will not terminate**.

while true: x=x+1;

 

 

*) This is where my knowledge is limited; how to express this in a formally and mathematically correct way that agrees with the mathematical proofs and the science behind the actor model. 
**) In reality of course there will be a limit for the size of variable x and the program could terminate.

Edited by Ghideon
Link to post
Share on other sites

So how is that n proven to exist in the Actor system?

What you're saying reminds me of the fact that e.g. any strictly decreasing sequence of ordinals is, in fact, finite, even though (if the initial value is infinite) it can be arbitrarily long. However, I still don't see what it is about the Actor system that forces the "stop" message to be eventually acted on.

Link to post
Share on other sites
3 hours ago, uncool said:

So how is that n proven to exist in the Actor system?

After some more reading I think it is kind of the other way around; unbounded nondeterminism states that the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be serviced*. With means that by definition, n has to exist.

Dijkstra argued that it is impossible to implement systems with unbounded nondeterminism. Hewitt argues that the actor model has the property of unbounded nondeterminism built in, allowing computations that cannot be implemented by Turing Machines. Hewitt has based a justification on metastability of electronics**: "There is no bound that can be placed on how long it takes a computational circuit called an arbiter to settle"****. 

I have not yet read the Clinger paper*** that according to wikipedia contains a mathematical treatment of the actor model and unbounded nondeterminism. 

On 5/5/2021 at 12:57 AM, uncool said:

if the "stop" message can be postponed for an unbounded time, why it couldn't be postponed forever,

My understanding at this time is that Dijkstra, Hewitt and the actor model is: if the "stop" message is can't be postponed forever why can it still be postponed for an unbounded time? (I am not claiming that your question is wrong, just modifying it to illustrate my understanding)

 

Sources:
*) https://en.wikipedia.org/wiki/Unbounded_nondeterminism
**) https://en.wikipedia.org/wiki/Metastability_(electronics)
***) https://dspace.mit.edu/bitstream/handle/1721.1/6935/AITR-633.pdf?sequence=2ActorLite
****)https://arxiv.org/vc/arxiv/papers/1008/1008.1459v8.pdf

 

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.