1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 by Aranda et al. $\endgroup$ Jul 13 at 9:39
  • $\begingroup$ @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. $\endgroup$
    – Timothy
    Jul 15 at 1:55
0
$\begingroup$

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<value> then head<value, left, right>;
        when write(new_value) then head<new_value, left, right>;
        when move_left(unused) then
            new (new_right) (
            left(new_value, new_left) head<new_value, new_left, new_right> ;
            | cell<value, new_right, right> ; )
        when move_right(unused) then
            new (new_left) (
            right(new_value, new_right) head<new_value, new_left, new_right> ;
            | cell<value, new_left, left> ; )
    end
    when cell(value, top, bottom) then top<value, bottom> ;
    when tape_end(channel) then
        new (new_channel) (channel<blank, new_channel> tape_end<new_channel> ;)
end))
|
(new (left) new (right) tape_end<left> head<blank, left, right> tape_end<right>;)

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.