Turing completeness of simple P systems 

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₁, r₂ and r₃ denote registers and k denotes a non-negative binary integer constant.
Instruction (EQ r₁ r₂ r₃) or (EQ r₁ k r₃):
Assume that j denotes the content of r₃. If the content of r₁ equals (i) the content of r₂ or (ii) the constant k, then the execution of M continues at the j-th instruction. If the content of r₁ does not equal (i) the content of r₂ or (ii) the constant k, then the execution of M continues at the next instruction in the sequence.

• Instruction (SET r₁ r₂) or (SET r₁ k): The content of r₁ is replaced by (i) the content of r₂ or (ii) the constant k.

• Instruction (ADD r₁ r₂) or (ADD r₁ k): The content of r₁ is replaced by (i) the sum of the contents of r₁ and r₂ or (ii) the sum of the contents of r₁ and constant k.

• Instruction (READ r₁): One bit is read into r₁, so the numerical value of r₁ 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₁; a₂; : : : ; a_k, a_i 2 Z, 1 i k, is encoded as 10^a1 10^a2 1 : : : 10^ak 1. Following [19] as an example, the sequence [3; 0; 2] is represented by the integer 281₍₁₀₎ = 100011001₍₂₎.

2. A self-delimiting representation of a sequence of bits b₁b₂ b_k, b_i 2 f0; 1g,

• i k, is encoded as 1b₁1b₂ 1b_k Note, if used to represent a positive integer n in base 2, then we need only O(k) = O(log₂ 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