Church-Turing thesis is outdated

[altaylar2000]

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 April 3, 2021 by altaylar2000

[Ghideon]

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?

 

[altaylar2000]

3 minutes ago, Ghideon said:

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

ok, I found it especially for you. Although what has been written is enough

page 9

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

[fredreload]

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.

[Ghideon]

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?)

[uncool]

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

[Ghideon]

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

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 x_i has at most one pending event, every pending event in the sequence becomes realized. Hence the sequence

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 May 4, 2021 by Ghideon
grammar and clarity

[uncool]

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.

[Ghideon]

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)n∈N 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 May 5, 2021 by Ghideon

[uncool]

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.

[Ghideon]

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

 

[Holmes]

On 4/3/2021 at 3:52 AM, altaylar2000 said:

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.

I don't understand what you mean by the thesis is "outdated", here's the thesis briefly (from Wikipedia)

Quote

the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. 

So what's outdated?

[Kartazion]

5 hours ago, Holmes said:

I don't understand what you mean by the thesis is "outdated", here's the thesis briefly (from Wikipedia)

So what's outdated?

I think the OP wanted to quote reasons from an article without giving the source of it. Indeed it implies the physical Church-Turing thesis and non-deterministic computation.

[Holmes]

On 6/28/2021 at 8:04 PM, Kartazion said:

I think the OP wanted to quote reasons from an article without giving the source of it. Indeed it implies the physical Church-Turing thesis and non-deterministic computation.

Can you give an example of a non-deterministic computation?

Computability, "computation", is defined as a wholly deterministic process so I do not see how we can have a non-deterministic computation.

Edited July 5, 2021 by Holmes

[Ghideon]

3 hours ago, Holmes said:

Can you give an example of a non-deterministic computation?

In addition to the Actor model already mentioned in this thread one example is Petri nets* where multiple transitions are enabled at the same time. 

 

 

*)https://en.wikipedia.org/wiki/Petri_net

[Holmes]

8 minutes ago, Ghideon said:

In addition to the Actor model already mentioned in this thread one example is Petri nets* where multiple transitions are enabled at the same time. 

*)https://en.wikipedia.org/wiki/Petri_net

Yes I know there are non-deterministic systems, but there is no concept of non-determinism in computation, in mathematics or arithmetic for example.

All theories of computability (Turing machines, Lambda calculus) are fully deterministic.

For example calculating the square root of Pi is deterministic, the same steps performed, always yield the same result.

Edited July 5, 2021 by Holmes

[Ghideon]

1 minute ago, Holmes said:

Yes I know there are non-deterministic systems, but there is no concept of non-determinism in computation, in mathematics or arithmetic for example.

All theories of computability (Turing machines, Lambda calculus) are fully deterministic.

Please provide a reference backing that statement.

Is a nondeterministic Turing machine is fully deterministic?

[studiot]

8 minutes ago, Holmes said:

but there is no concept of non-determinism in computation, in mathematics or arithmetic for example.

In another thread you stated that you are not a Mathematician.

Perhaps you might like to enquire of your favourite Mathematician if this claim is in fact true as there are non deterministic computations available in Mathematics that were first discovered in the 1960s by Mandelbrot and later by someone (I'm not sure whom) extending Ullam and Von Neuman's work from the 1940s.

[Holmes]

1 minute ago, Ghideon said:

Please provide a reference backing that statement.

Which statement? this one "All theories of computability (Turing machines, Lambda calculus) are fully deterministic."?

Well both lambda calculus and Turing machines are regarded as logically equivalent systems for describing computability.

Computability means literally calculating, doing what humans can do (and at one time only humans could do).

All the rules of arithmetic for example can be described using a Turing machine or lambda calculus.

1 minute ago, Ghideon said:

Is a nondeterministic Turing machine is fully deterministic?

There are concepts of non-deterministic Turing machines but these do not appear in computability theory.

 

3 minutes ago, studiot said:

In another thread you stated that you are not a Mathematician.

Perhaps you might like to enquire of your favourite Mathematician if this claim is in fact true as there are non deterministic computations available in Mathematics that were first discovered in the 1960s by Mandelbrot and later by someone (I'm not sure whom) extending Ullam and Von Neuman's work from the 1940s.

The Mandelbrot set is fully deterministic.

[studiot]

36 minutes ago, Holmes said:

The Mandelbrot set is fully deterministic.

So what ?

Mandelbrot worked on many things.

Your response it a bit like saying Maxwell's theory of colour is wrong because he wrote the laws of thermodynamics.

Edited July 5, 2021 by studiot

[Ghideon]

10 minutes ago, Holmes said:

Which statement? this one "All theories of computability (Turing machines, Lambda calculus) are fully deterministic."?

Yes. And also:

12 minutes ago, Holmes said:

There are concepts of non-deterministic Turing machines but these do not appear in computability theory.

The theories I am familiar with includes for instance nondeterministic finite automaton and analysis of nondeterministic algorithms. Maybe you are using different definitions than used in the papers discussed in this thread.

[Holmes]

Mathematics is deterministic, computability theory is a logical theory that reduces mathematics to logic, there are at least two approaches to computability theory Turing machines and lambda calculus, it has been proven that Turing machines and lambda calculus - though very different - are logically equivalent, both are of course deterministic.

This is why I asked for an example of a "non-deterministic computation".

 

Edited July 6, 2021 by Holmes

[Kartazion]

45 minutes ago, Holmes said:

This is why I asked for an example of a "non-deterministic computation".

Schematic example of Comparison of deterministic and Non-deterministic computation. 

 

[Holmes]

2 minutes ago, Kartazion said:

Schematic example of Comparison of deterministic and Non-deterministic computation. 

 

I may not have made myself clear.

I did not say there are not models of non-deterministic systems there are. 

I said that mathematics and with it computability theory are wholly deterministic.

A "computation" is by definition repeatable (every time we do the computation, calculation we get the same answer, different people doing the same computation get the same answer).

Please show me an equation that gives different results for different people, can you do that? no.

1 + 1 = 2, today, next week, for me for you.

[Ghideon]

1 hour ago, Holmes said:

This is why I asked for an example of a "non-deterministic computation".

I gave you examples. 

1 hour ago, Holmes said:

Mathematics is deterministic, computability theory is a logical theory that reduces mathematics to logic, there are at least two approaches to computability theory Turing machines and lambda calculus, it has been proven that Turing machines and lambda calculus - though very different - are logically equivalent, both are of course deterministic.

 

Again; according to what sources? This thread is interesting and it would be unfortunate if a good opportunity for discussion is missed due to different definitions being used.