Get Complete Project Material File(s) Now! »

**Chapter 3 Turing completeness of simple P systems**

This chapter shows that simple P systems, introduced in Chapter 2, are Turing com-plete (i.e. can compute anything a Turing machine [42, 74] can compute) and universal (i.e. can simulate an arbitrary Turing machine with input), by proving that simple P systems can simulate all READ-enhanced register machines [9]. This register ma-chine model allows input data (denoted as a sequence of bits or characters), which are accessed using READ instructions that return the next unread bit. Several universality results in membrane systems have used register machines that need to store input data in the registers, e.g. [49].

This chapter is organized as follows. Section 3.1 recalls the de nition of READ-enhanced register machines [9]. Section 3.2 presents simple P systems that simulate READ-enhanced register machines (with binary input data). Additionally, using the greatest common divisor (GCD) function, this section provides two simple P systems, obtained via direct and indirect approaches, respectively. Finally, a summary of this chapter is given in Section 3.3.

**Register machines**

A register machine, as presented in [9], has n > 1 instructions and m > 0 registers, where each register may contain an arbitrarily large non-negative integer. Register machines are Turing-complete and universal. A register machine program consists of a nite list of instructions, EQ, SET, ADD, READ and HALT, with the restriction that the HALT instruction appears only once, as the last instruction of the list, followed by input data. The rst instruction of a program is indexed by the value 0. Here, a program is presented in symbolic instruction form.

Register machine instructions A set of instructions of a register machine M [9] is listed below. In the instructions below, r_{1}, r_{2} and r_{3} denote registers and k denotes a non-negative binary integer constant.

Instruction (EQ r_{1} r_{2} r_{3}) or (EQ r_{1} k r_{3}):

Assume that j denotes the content of r_{3}. If the content of r_{1} equals (i) the content of r_{2} or (ii) the constant k, then the execution of M continues at the j-th instruction. If the content of r_{1} does not equal (i) the content of r_{2} or (ii) the constant k, then the execution of M continues at the next instruction in the sequence.

- Instruction (SET r
_{1}r_{2}) or (SET r_{1}k): The content of r_{1}is replaced by (i) the content of r_{2}or (ii) the constant k.

- Instruction (ADD r
_{1}r_{2}) or (ADD r_{1}k): The content of r_{1}is replaced by (i) the sum of the contents of r_{1}and r_{2}or (ii) the sum of the contents of r_{1}and constant k.

- Instruction (READ r
_{1}): One bit is read into r_{1}, so the numerical value of r_{1}becomes either 0 or 1. Any attempt to read past the last data-bit results in a run-time error.

- Instruction (HALT):

This is the last instruction of a register machine program.

**Input data**

In a register machine program, its input data, denoted as a sequence of bits (or characters), follows immediately after the halt instruction. Note, some programs may not have input data and it is up to the program to know how to process the data in the chosen encoding format. A variation of the following two encoding formats is used to represent register machine input data within a simple P system.

- A sequence of non-negative integers, a
_{1}; a_{2}; : : : ; a_{k}, a_{i}2 Z, 1 i k, is encoded as 10^{a}1 10^{a}2 1 : : : 10^{a}k 1. Following [19] as an example, the sequence [3; 0; 2] is represented by the integer 281_{(10)}= 100011001_{(2)}.

- A self-delimiting representation of a sequence of bits b
_{1}b_{2}b_{k}, b_{i}2 f0; 1g,

- i k, is encoded as 1b
_{1}1b_{2}1b_{k}Note, if used to represent a positive integer n in base 2, then we need only O(k) = O(log_{2}n) bits, but twice the number of ‘real’ bits.

**Run-time errors**

A register machine program, with n 1 instructions, can encounter the following run-time errors

- Illegal branch error: This error occurs when an EQ instruction is executed where the value indicated by its third register is greater or equal to n.
- Under-read error: This error occurs if a register machine halts with unread input data, i.e. when the HALT instruction is encountered and there exist unread input data.
- Over-read error: This error occurs if a register machine attempts to read past the last data-bit, i.e. when a READ instruction is encountered and the entire input data has already been read.

**1 Introduction **

1.1 Membrane systems

1.2 Motivation

1.3 Thesis outline

1.4 Publications

**2 Membrane Systems **

2.1 Preliminaries

2.2 Transition P systems

2.3 Extensions and variants

2.4 Simple P systems

2.5 Summary

**3 Turing completeness of simple P systems **

3.1 Register machines

3.2 Universality results

3.3 Summary

**4 Traversal Algorithms in Membrane Systems **

4.1 Traversal algorithms

4.2 Tree traversal algorithms

4.3 Graph traversal algorithms

4.4 Summary

**5 The Firing Squad Synchronization Problem **

5.1 Synchronization

5.2 Phase-based decomposition of the FSSP

5.3 Static FSSP solution for graphs

5.4 Adaptive FSSP solution for trees

5.5 Summary

**6 The Disjoint Paths Problem**

6.1 Disjoint paths in digraphs

6.2 Edge-disjoint paths solution

6.3 Node-disjoint paths solution

6.4 Summary

**7 Conclusions**

GET THE COMPLETE PROJECT

Distributed Algorithms in Membrane Systems