<p>I found that the answer is yes, you can construct a Turing Machine in the Pi calculus with just one replication operator. Here is how I constructed the tape for a Turing machine using the syntax of <a href="https://github.com/glenbraun/JsonPi" rel="nofollow noreferrer">this</a> interpreter.</p>
<pre><code>(!(choose
    when head(value, left, right) then
    choose
        when read&lt;value&gt; then head&lt;value, left, right&gt;;
        when write(new_value) then head&lt;new_value, left, right&gt;;
        when move_left(unused) then
            new (new_right) (
            left(new_value, new_left) head&lt;new_value, new_left, new_right&gt; ;
            | cell&lt;value, new_right, right&gt; ; )
        when move_right(unused) then
            new (new_left) (
            right(new_value, new_right) head&lt;new_value, new_left, new_right&gt; ;
            | cell&lt;value, new_left, left&gt; ; )
    end
    when cell(value, top, bottom) then top&lt;value, bottom&gt; ;
    when tape_end(channel) then
        new (new_channel) (channel&lt;blank, new_channel&gt; tape_end&lt;new_channel&gt; ;)
end))
|
(new (left) new (right) tape_end&lt;left&gt; head&lt;blank, left, right&gt; tape_end&lt;right&gt;;)
</code></pre>
<p>To complete the Turing machine you just need to add the finite state machine to interact with this tape on the channels &quot;read&quot;, &quot;write&quot;, &quot;move_left&quot;, and &quot;move_right&quot;.  This can be done by adding a &quot;when&quot; clause listening on its own channel for each state of the finite state machine, which then signals/queries the tape and signals the appropriate next state of the finite state machine.</p>
<p>One interesting property of this solution is that it does not make use of recursive channel types, which the second edition of Practical Foundations for Programming Languages by Robert Harper suggests is required for the Pi Calculus to be universal.</p>

CC BY-SA 4.0
2021-07-15T01:49:23.430Z
2021-07-15T01:49:23.430Z
Timothy
<p>See title.  If it is not universal, then how is the power of the pi calculus with this restriction characterized?</p>

CC BY-SA 4.0
2021-07-13T09:39:57.463Z
Not sure why this is voted down, this is an interesting question. @Timothy why do you think that you need more than one replication? Such questions are subtle, and depend on exactly the variant of pi-calcululs used. See for a start: [*On Recursion, Replication and Scope Mechanisms in Process Calculi*](http://www.lix.polytechnique.fr/~fvalenci/papers/fmco07.pdf) by Aranda et al.
Martin Berger
CC BY-SA 4.0
2021-07-15T01:55:44.733Z
@MartinBerger Thank you for showing interest in my question.  Please consider taking a look at the construction I have provided in my answer, hopefully you will find it also interesting.
Timothy
<process-algebra><pi-calculus>
Can you embed a Turing Machine into the Pi calculus with just one replication operator?
Timothy
# Can you embed a Turing Machine into the Pi calculus with just one replication operator?

(Asked by: username_0 on 2021-07-12)

See title. If it is not universal, then how is the power of the pi calculus with this restriction characterized?

**Tags:** process-algebra, pi-calculus

> **Comments:**
> **username_1**: Not sure why this is voted down, this is an interesting question. @username_0 why do you think that you need more than one replication? Such questions are subtle, and depend on exactly the variant of pi-calcululs used. See for a start: [*On Recursion, Replication and Scope Mechanisms in Process Calculi*](http://www.lix.polytechnique.fr/~fvalenci/papers/fmco07.pdf) by Aranda et al.  
> **username_0**: @MartinBerger Thank you for showing interest in my question.  Please consider taking a look at the construction I have provided in my answer, hopefully you will find it also interesting.  

---

## 1 answers

### Answer by username_0 on 2021-07-15. Score: 0 | Accepted answer

I found that the answer is yes, you can construct a Turing Machine in the Pi calculus with just one replication operator. Here is how I constructed the tape for a Turing machine using the syntax of this interpreter.
(!(choose
    when head(value, left, right) then
    choose
        when read then head;
        when write(new_value) then head;
        when move_left(unused) then
            new (new_right) (
            left(new_value, new_left) head ;
            | cell ; )
        when move_right(unused) then
            new (new_left) (
            right(new_value, new_right) head ;
            | cell ; )
    end
    when cell(value, top, bottom) then top ;
    when tape_end(channel) then
        new (new_channel) (channel tape_end ;)
end))
|
(new (left) new (right) tape_end head tape_end;)

To complete the Turing machine you just need to add the finite state machine to interact with this tape on the channels "read", "write", "move_left", and "move_right".  This can be done by adding a "when" clause listening on its own channel for each state of the finite state machine, which then signals/queries the tape and signals the appropriate next state of the finite state machine.
One interesting property of this solution is that it does not make use of recursive channel types, which the second edition of Practical Foundations for Programming Languages by Robert Harper suggests is required for the Pi Calculus to be universal.


---

