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 . 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. .
This chapter is organized as follows. Section 3.1 recalls the de nition of READ-enhanced register machines . 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.
A register machine, as presented in , 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  is listed below. In the instructions below, r1, r2 and r3 denote registers and k denotes a non-negative binary integer constant.
Instruction (EQ r1 r2 r3) or (EQ r1 k r3):
Assume that j denotes the content of r3. If the content of r1 equals (i) the content of r2 or (ii) the constant k, then the execution of M continues at the j-th instruction. If the content of r1 does not equal (i) the content of r2 or (ii) the constant k, then the execution of M continues at the next instruction in the sequence.
- Instruction (SET r1 r2) or (SET r1 k): The content of r1 is replaced by (i) the content of r2 or (ii) the constant k.
- Instruction (ADD r1 r2) or (ADD r1 k): The content of r1 is replaced by (i) the sum of the contents of r1 and r2 or (ii) the sum of the contents of r1 and constant k.
- Instruction (READ r1): One bit is read into r1, so the numerical value of r1 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.
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, a1; a2; : : : ; ak, ai 2 Z, 1 i k, is encoded as 10a1 10a2 1 : : : 10ak 1. Following  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 b1b2 bk, bi 2 f0; 1g,
- i k, is encoded as 1b11b2 1bk Note, if used to represent a positive integer n in base 2, then we need only O(k) = O(log2 n) bits, but twice the number of ‘real’ bits.
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.1 Membrane systems
1.3 Thesis outline
2 Membrane Systems
2.2 Transition P systems
2.3 Extensions and variants
2.4 Simple P systems
3 Turing completeness of simple P systems
3.1 Register machines
3.2 Universality results
4 Traversal Algorithms in Membrane Systems
4.1 Traversal algorithms
4.2 Tree traversal algorithms
4.3 Graph traversal algorithms
5 The Firing Squad Synchronization Problem
5.2 Phase-based decomposition of the FSSP
5.3 Static FSSP solution for graphs
5.4 Adaptive FSSP solution for trees
6 The Disjoint Paths Problem
6.1 Disjoint paths in digraphs
6.2 Edge-disjoint paths solution
6.3 Node-disjoint paths solution
GET THE COMPLETE PROJECT
Distributed Algorithms in Membrane Systems