Relationships Between Nondeterministic and Deterministic Tape Complexities

Mối quan hệ giữa độ phức tạp băng từ không tất định và tất định*

Walter J. Savitch

Department of Applied Physics and Information Science, University of California, San Diego, La Jolla, California 92037

Nhận ngày 29 tháng 8, 1969

Lượng bộ nhớ cần thiết để mô phỏng một máy Turing bị giới hạn băng từ không tất định trên một máy Turing tất định được nghiên cứu. Các kết quả bao gồm những điều sau: Định lý. Một máy Turing bị giới hạn băng từ $L(n)$ không tất định có thể được mô phỏng bởi một máy Turing bị giới hạn băng từ $[L(n)]^2$ tất định, với điều kiện $L(n) \geq \log_2 n$. Các tính toán của các máy không tất định được chỉ ra là tương ứng với các phép luồn qua của một số mê cung nhất định. Sự tương ứng này được sử dụng để tạo ra một tập cụ thể, cụ thể là tập tất cả các mã hóa của các mê cung có thể luồn qua, sao cho, nếu có bất kỳ tập nào phân biệt các lớp độ phức tạp băng từ không tất định với các lớp độ phức tạp băng từ tất định, thì đây là một tập như vậy.

Department of Applied Physics and Information Science, University of California, San Diego, La Jolla, California 92037

Received August 29, 1969

The amount of storage needed to simulate a nondeterministic tape bounded Turing machine on a deterministic Turing machine is investigated. Results include the following: Theorem. A nondeterministic $L(n)$-tape bounded Turing machine can be simulated by a deterministic $[L(n)]^2$-tape bounded Turing machine, provided $L(n) \geq \log_2 n$. Computations of nondeterministic machines are shown to correspond to threadings of certain mazes. This correspondence is used to produce a specific set, namely the set of all codings of threadable mazes, such that, if there is any set which distinguishes nondeterministic tape complexity classes from deterministic tape complexity classes, then this is one such set.

Giới thiệu

Introduction

Một bài toán mở nổi tiếng trong lý thuyết ngôn ngữ hình thức và độ phức tạp tính toán là quyết định liệu có tồn tại hay không một ngôn ngữ phi ngữ cảnh nhạy cảm không tất định, tức là quyết định liệu có hay không một tập được chấp nhận bởi một ôtômát bị giới hạn tuyến tính không tất định, nhưng không được chấp nhận bởi bất kỳ máy tất định tương tự nào. Trong bài báo này, chúng tôi đưa ra một số câu trả lời từng phần cho một khái quát hóa tự nhiên của bài toán này. Chúng tôi cố gắng trả lời câu hỏi sau: "Cho một máy Turing bị giới hạn băng không tất định chấp nhận một tập $A$, một máy Turing tất định cần bao nhiêu bộ nhớ bổ sung để nhận biết $A$?"

A well-known open problem in the theory of formal languages and computational complexity is to decide whether or not there exists a nondeterministic context-sensitive language, that is, to decide whether or not there is a set which is accepted by a nondeterministic linear bounded automaton, but is accepted by no such deterministic machine. In this paper, we give some partial answers to a natural generalization of this problem. We attempt to answer the following question: "Given a nondeterministic tape bounded Turing machine which accepts a set $A$, how much addition storage does a deterministic Turing machine require to recognize $A$?"

Cụ thể hơn, chúng tôi chỉ ra rằng bất kỳ máy Turing bị giới hạn băng $L(n)$ không tất định nào cũng có thể được mô phỏng bởi một máy Turing bị giới hạn băng $[L(n)]^2$ tất định, với điều kiện $L(n) \geq \log_2 n$. Do đó, đặc biệt, mọi ngôn ngữ nhạy cảm ngữ cảnh đều có thể được nhận biết trong bộ nhớ tất định $n^2$, trong đó $n$ là độ dài của đầu vào. Như một hệ quả của chứng minh định lý này, chúng tôi thu được rằng nếu một ngôn ngữ nhạy cảm ngữ cảnh được

More specifically, we show that any nondeterministic $L(n)$-tape bounded Turing machine can be simulated by a deterministic $[L(n)]^2$-tape bounded Turing machine, provided $L(n) \geq \log_2 n$. Thus, in particular, every context-sensitive language can be recognized within deterministic storage $n^2$, where $n$ is the length of the input. As a corollary of the proof of this theorem, we get that if a context-sensitive language is

• Công trình này dựa trên một phần luận án tiến sĩ của tác giả tại Khoa Toán học của University of California, Berkeley. Phần lớn các kết quả đã được công bố trong [9]. Một phần của nghiên cứu này được thực hiện khi tác giả là National Science Foundation Graduate Fellow.

• This work is based on a portion of the author's doctoral dissertation in the Department of Mathematics of the University of California, Berkeley. Most of the results were announced in [9]. Part of this research was done while the author was a National Science Foundation Graduate Fellow.

chấp nhận bởi một ôtômát bị giới hạn tuyến tính không tất định trong thời gian đa thức, thì ngôn ngữ đó được chấp nhận bởi một máy Turing tất định trong bộ nhớ $n \log_2 n$. Cũng chỉ ra rằng nếu các lớp độ phức tạp băng không tất định và tất định bằng nhau đối với các hàm "nhỏ", thì chúng cũng bằng nhau đối với các hàm "lớn".

accepted by a nondeterministic linear bounded automaton within polynomial time, then the language is accepted by a deterministic Turing machine within storage $n \log_2 n$. It is also shown that if nondeterministic and deterministic tape complexity classes are equal for "small" functions, then they are equal for "large" functions.

Khái niệm mê cung được hình thức hóa và các tính toán của các máy không tất định được liên hệ với các cách đi xuyên qua của một số mê cung nhất định. Mối liên hệ này được sử dụng để thu được một tập cụ thể, cụ thể là tập các mã hóa của các mê cung có thể đi xuyên qua, sao cho, nếu có bất kỳ tập nào phân biệt các lớp độ phức tạp băng không tất định với các lớp độ phức tạp băng tất định, thì đây là một tập như vậy. Nghĩa là, có một máy Turing không tất định chấp nhận các mã hóa của các mê cung có thể đi xuyên qua trong bộ nhớ $\log_2 n$. Ngoài ra, nếu có một máy Turing tất định chấp nhận chúng trong cùng bộ nhớ, $\log_2 n$, thì với mọi hàm bộ nhớ $L(n) \geq \log_2 n$, bất kỳ máy Turing bị giới hạn băng $L(n)$ không tất định nào cũng có thể được kích thích bởi một máy Turing bị giới hạn băng $L(n)$ tất định.

The notion of a maze is formalized and computations of nondeterministic machines are related to threadings of certain mazes. This relation is used to obtain a specific set, namely the set of codings of threadable mazes, such that, if there is any set which distinguishes nondeterministic tape complexity classes from deterministic tape complexity classes, then this is one such set. That is, there is a nondeterministic Turing machine which accepts the codings of threadable mazes within storage $\log_2 n$. Also, if there is a deterministic Turing machine which accepts them within the same storage, $\log_2 n$, then, for every storage function $L(n) \geq \log_2 n$, any nondeterministic $L(n)$-tape bounded Turing machine can be stimulated by a deterministic $L(n)$-tape bounded Turing machine.

Mô hình máy

Machine Model

Thiết bị được nghiên cứu trong bài báo này là Máy Turing nhiều băng. Theo thuật ngữ của [3], đây là một máy Turing với hữu hạn băng lưu trữ vô hạn hai chiều và một băng đầu vào chỉ đọc được cung cấp các dấu kết thúc. Chúng tôi chỉ đưa ra một định nghĩa không chính thức về thiết bị này. Một máy Turing nhiều băng (sau đây gọi đơn giản là máy Turing) là một bộ điều khiển trạng thái hữu hạn được gắn với một băng đầu vào chỉ đọc và hữu hạn các băng lưu trữ đọc/ghi. Các băng được chia thành các ô. Mỗi ô của một băng lưu trữ có khả năng chứa một ký hiệu từ bảng chữ cái băng lưu trữ hữu hạn $\Gamma$. Băng đầu vào sẽ luôn chứa một chuỗi hữu hạn $w$ gồm các ký hiệu từ bảng chữ cái đầu vào hữu hạn $\Sigma$. Chuỗi $w$ được phân cách bởi hai ký hiệu không thuộc $\Sigma$ được gọi là dấu kết thúc bên trái và dấu kết thúc bên phải. Mỗi băng có một đầu đọc giao tiếp với bộ điều khiển hữu hạn.

The device studied in this paper is the multitape Turing Machine. In the terminology of [3], it is a Turing machine with finitely many two-way infinite storage tapes and a read only input tape provided with end markers. We shall give only an informal definition of the device. A multitape Turing machine (hereafter called simply Turing machine) is a finite state control attached to a read only input tape and finitely many read/write storage tapes. The tapes are divided into squares. Each square of a storage tape is capable of holding one symbol from the finite storage tape alphabet $\Gamma$. The input tape will always contain a finite string $w$ of symbols from the finite input alphabet $\Sigma$. The string $w$ is separated by two symbols not in $\Sigma$ called left and right end markers. Each tape has one head communicating with the finite control.

Tại bất kỳ thời điểm nào, mỗi đầu đọc sẽ quét một ô trên băng của nó và bộ điều khiển sẽ ở một trạng thái. Phụ thuộc vào trạng thái này và các ký hiệu được các đầu đọc quét, máy sẽ, trong một bước, chuyển sang một trạng thái khác, ghi đè một ký hiệu trên ô đang được quét của mỗi băng lưu trữ của nó, rồi dịch chuyển một số đầu đọc của nó (có thể bao gồm cả đầu đọc đầu vào) sang trái hoặc phải một ô. Bộ điều khiển hữu hạn được thiết kế sao cho đầu đọc đầu vào sẽ không bao giờ rời khỏi đoạn băng chứa $w$ và các dấu kết thúc. Máy được gọi là tất định nếu chỉ có một hành động khả dĩ tại mỗi bước. Máy được gọi là không tất định nếu có hữu hạn hành động khả dĩ tại mỗi bước.

At any point in time, each head will scan one square on its tape and the control will be in one state. Depending on this state and the symbols scanned by the heads, the machine will, in one step, assume another state, overwrite a symbol on the scanned square of each of its storage tapes, and then shift some of its heads (including possibly the input head) either left or right one square. The finite control is designed so that the input head will never leave the segment of tape containing $w$ and the end markers. The machine is said to be deterministic if there is only one possible action at each step. It is said to be nondeterministic if there are finitely many possible actions at each step.

Một số trạng thái được phân biệt và gọi là các trạng thái chấp nhận và một trạng thái được phân biệt và gọi là trạng thái ban đầu. Chúng tôi nói máy tất định $Z$ chấp nhận chuỗi đầu vào $w$ trên $\Sigma$ nếu $Z$ đi vào một trạng thái chấp nhận sau hữu hạn bước, khi bắt đầu ở trạng thái ban đầu, với tất cả các băng lưu trữ trống, $w$ trên băng đầu vào và đầu đọc đầu vào đang quét dấu kết thúc bên trái. Định nghĩa này cũng giống trong trường hợp $Z$ là không tất định ngoại trừ việc chúng ta chỉ yêu cầu rằng có một chuỗi hữu hạn các bước khả dĩ dẫn đến một trạng thái chấp nhận, bắt đầu từ cấu hình ban đầu được mô tả ở trên.

Some states are distinguished and called accepting states and one state is distinguished and called the initial state. We say the deterministic machine $Z$ accepts the input string $w$ over $\Sigma$ if $Z$ enters an accepting state after finitely many steps, when started in the initial state, with all storage tapes blank, $w$ on its input tape and its input head scanning the left end marker. The definition is the same in the case $Z$ is nondeterministic except that we merely require that there be a possible finite sequence of steps leading to an accepting state, starting from the initial configuration described above.

Định nghĩa. Giả sử $L(n)$ là một hàm trên các số tự nhiên, $Z$ là một máy Turing (tất định hoặc không tất định), và $A$ là một tập các chuỗi trên bảng chữ cái đầu vào của $Z$. $Z$ được nói là chấp nhận tập $A$ trong bộ nhớ $L(n)$ nếu

Definition. Suppose $L(n)$ is a function on the natural numbers, $Z$ is a Turing machine (deterministic or nondeterministic), and $A$ is a set of strings over the input alphabet of $Z$. $Z$ is said to accept the set $A$ within storage $L(n)$ provided that

(i) với mỗi chuỗi $w$ trong $A$, có ít nhất một tính toán khả dĩ của $Z$ chấp nhận $w$ và trong đó mỗi đầu đọc băng lưu trữ quét nhiều nhất $L(|w|)$ ô, và

(i) for each string $w$ in $A$, there is at least one possible computation of $Z$ which accepts $w$ and in which each storage tape head scans at most $L(|w|)$ squares, and

(ii) $Z$ không chấp nhận chuỗi nào không thuộc $A$. $|w|$ là độ dài của chuỗi, $w$.

(ii) $Z$ accepts no string not in $A$. $|w|$ is the length of the string, $w$.

Trong bài báo này chúng tôi chỉ xem xét tốc độ tăng trưởng của các hàm bộ nhớ. Nghĩa là, đối với mục đích của chúng tôi, các hàm bộ nhớ $L(n)$ và $\epsilon L(n)$ là giống nhau, với mọi hằng số $\epsilon > 0$. Sự đồng nhất này của các hàm xuất phát từ thực tế rằng các máy Turing của chúng tôi được phép có các bảng chữ cái băng lưu trữ hữu hạn tùy ý. Vì vậy, bất kỳ máy Turing nào hoạt động với bộ nhớ $L(n)$ đều có thể được sửa đổi để hoạt động với bộ nhớ $\epsilon L(n)$ và vẫn chấp nhận cùng một tập băng. (Xem, ví dụ, [3].) Chúng tôi giả sử người đọc quen thuộc với các kỹ thuật giảm băng như vậy.

In this paper we are considering only the growth rates of storage functions. That is, for our purposes, the storage functions $L(n)$ and $\epsilon L(n)$ are the same, for any constant $\epsilon > 0$. This identification of functions follows from the fact that our Turing machines are allowed arbitrary finite storage tape alphabets. Thus, any Turing machine which operates in storage $L(n)$ can be modified to operate in storage $\epsilon L(n)$ and still accept the same set of tapes. (See, for example, [3].) We assume the reader is familiar with such tape reduction techniques.

Trong phần tiếp theo, đôi khi sẽ thuận tiện khi giả sử rằng các hàm lưu trữ là "tốt". Điều kiện về tính tốt mà chúng ta muốn là các hàm phải đo được [4].

In what follows, it will sometimes be convenient to assume that the storage functions are "nice". The niceness condition we want is that the functions be measurable [4].

Định nghĩa. Một hàm $L(n)$ được gọi là đo được nếu tồn tại một máy Turing chỉ với một băng lưu trữ sao cho, với bất kỳ đầu vào nào có độ dài $n$, máy sẽ dừng sau một quá trình tính toán trong đó đầu đọc của băng lưu trữ quét chính xác $L(n)$ ô.

Definition. A function $L(n)$ is said to be measurable if there is some Turing machine with just one storage tape such that, given any input of length $n$, the machine will halt after a computation in which the storage tape head scans exactly $L(n)$ squares.

Có vẻ như tất cả các hàm lưu trữ thông dụng $L(n) \geq \log_2 n$ đều đo được. Cụ thể, mọi đa thức theo $n$ và $\log_2 n$ đều đo được.

Apparently, all common storage functions $L(n) \geq \log_2 n$ are measurable. In particular, any polynomial in $n$ and $\log_2 n$ is measurable.

Mô phỏng xác định của các máy Turing không xác định

Deterministic Simulation of Nondeterministic Turing Machines

Định lý 1. Nếu một tập, $A$, được chấp nhận bởi một máy Turing không xác định, $Z_N$, trong phạm vi lưu trữ $L(n) \geq \log_2 n$, thì $A$ được chấp nhận bởi một máy Turing xác định nào đó, $Z_D$, trong phạm vi lưu trữ $[L(n)]^2$.

Theorem 1. If a set, $A$, is accepted by a nondeterministic Turing machine, $Z_N$, within storage $L(n) \geq \log_2 n$, then $A$ is accepted by some deterministic Turing machine, $Z_D$, within storage $[L(n)]^2$.

Chứng minh. Định lý được chứng minh bằng cách đưa ra một thuật toán theo đó $Z_D$ có thể mô phỏng các phép tính của $Z_N$. Thuật toán này tương tự như thuật toán được Lewis, Stearns, và Hartmanis [7] sử dụng để chỉ ra rằng mọi ngôn ngữ phi ngữ cảnh đều được chấp nhận bởi một máy Turing xác định trong phạm vi lưu trữ $(\log_2 n)^2$.

Proof. The theorem is proved by exhibiting an algorithm whereby $Z_D$ can simulate the computations of $Z_N$. The algorithm is similar to that used by Lewis, Stearns, and Hartmanis [7] to show that every context-free language is accepted by a deterministic Turing machine within storage $(\log_2 n)^2$.

Giả sử máy Turing $Z_N$ có $k$ băng lưu trữ, bảng chữ cái của băng lưu trữ $\Gamma$, và tập trạng thái bên trong $Q$. Gọi $\Delta = Q \cup \Gamma \cup \{1, 2, *, \downarrow\}$, trong đó $\downarrow$ và $*$ là hai ký hiệu mới. Một mô tả tức thời (ID) của $Z_N$ là một chuỗi trên $\Delta$ có dạng pq u₁ ↓ v₁ u₂ ↓ v₂ ... uₖ ↓ vₖ, trong đó p là một số ở dạng ký hiệu dyadic¹ chỉ vị trí của đầu đọc đầu vào của $Z_N$, q là một phần tử của Q chỉ ra rằng bộ điều khiển hữu hạn của $Z_N$ đang ở trạng thái q, và $u_i, v_i$ là các phần tử của $\Gamma^*$, $i = 1, 2, ..., k$. $u_i ↓ v_i$ được hiểu là $u_i v_i$ là nội dung của băng lưu trữ thứ i của $Z_N$ và đầu đọc trên băng này đang quét ký hiệu đầu tiên của chuỗi $v_i$. Vì vậy, ngoại trừ nội dung của băng đầu vào, một ID của $Z_N$ là một mô tả hoàn chỉnh về một cấu hình của $Z_N$.

Suppose the Turing machine $Z_N$ has $k$ storage tapes, storage tape alphabet $\Gamma$, and internal state set $Q$. Let $\Delta = Q \cup \Gamma \cup \{1, 2, *, \downarrow\}$, where $\downarrow$ and $*$ are two new symbols. An instantaneous description (ID) of $Z_N$ is a string over $\Delta$ of the form pq u₁ ↓ v₁ u₂ ↓ v₂ ... uₖ ↓ vₖ, where p is a number in dyadic notation¹ indicating the position of the input head of $Z_N$, q is an element of Q indicating that the finite control of $Z_N$ is in state q, and $u_i, v_i$ are elements of $\Gamma^*$, $i = 1, 2, ..., k$. $u_i ↓ v_i$ is interpreted to mean that $u_i v_i$ is the contents of the ith storage tape of $Z_N$ and the head on this tape is scanning the first symbol of string $v_i$. Thus, except for the contents of the input tape, an ID of $Z_N$ is a complete description of a configuration of $Z_N$.

Vì $Z_N$ chấp nhận tập $A$ trong phạm vi lưu trữ $L(n) \geq \log_2 n$, nên suy ra rằng với mỗi chuỗi w có độ dài n được $Z_N$ chấp nhận, tồn tại một phép tính của $Z_N$ chấp nhận w trong đó mỗi ID có độ dài không vượt quá $cL(n)$. Hơn nữa, vì mỗi ID có độ dài nhiều nhất là $cL(n)$, phép tính cần không quá $2^{c'L(n)}$ bước. c và $c'$ là các hằng số chỉ phụ thuộc vào $Z_N$ chứ không phụ thuộc vào đầu vào w.

Since $Z_N$ accepts the set $A$ within storage $L(n) \geq \log_2 n$, it follows that for each string w of length n accepted by $Z_N$, there is a computation of $Z_N$ accepting w in which every ID has length not exceeding $cL(n)$. Furthermore, since each ID is of length at most $cL(n)$, the computation need take no more than $2^{c'L(n)}$ steps. c and $c'$ are constants depending only on $Z_N$ and not on the input w.

Trước hết chúng ta đưa ra thuật toán cho trường hợp: $L(n)$ là đo được.

We first give the algorithm for the case: $L(n)$ is measurable.

Với một đầu vào có độ dài n, $Z_D$ khởi tạo phép tính của nó bằng cách chia một trong các băng lưu trữ của nó thành $[c'L(n)] + 1$ khối (được gọi là các thanh ghi), mỗi khối có độ dài $[cL(n)]$, tiếp theo là $[c'L(n)] + 1$ khối (được gọi là các thẻ), mỗi khối có khả năng lưu trữ hoặc 0 hoặc 1. Nó có thể dễ dàng thực hiện việc này nếu $L(n)$ là đo được. [y] là số nguyên lớn nhất không vượt quá y. Lưu ý rằng mỗi thanh ghi có khả năng chứa bất kỳ ID nào của $Z_N$ trong đó phần không trắng của mỗi băng lưu trữ nhiều nhất là $L(n)$. $Z_D$ có một băng lưu trữ thứ hai cho công việc tạm thời.

Given an input of length n, $Z_D$ initializes its computation by dividing one of its storage tapes into $[c'L(n)] + 1$ blocks (called registers), each of length $[cL(n)]$, followed by $[c'L(n)] + 1$ blocks (called tags), each capable of storing either 0 or 1. This it can easily do if $L(n)$ is measurable. [y] is the largest integer not exceeding y. Note that each register is capable of holding any ID of $Z_N$ in which the nonblank portion of every storage tape is at most $L(n)$. $Z_D$ has a second storage tape for scratch work.

Ý tưởng của thuật toán như sau. $Z_D$ có chuỗi w làm đầu vào. Trong quá trình của thuật toán, $Z_D$ sẽ xem xét hai ID I, $I''$ được lưu trong các thanh ghi cụ thể. Với một m được chọn trước, nó sẽ cần kiểm tra xem, với đầu vào w, $Z_N$ có thể trong $2^m$ bước thay đổi cấu hình của nó từ I sang $I''$ hay không. Hơn nữa, $Z_D$ sẽ phải thực hiện nhiệm vụ này chỉ sử dụng m thanh ghi. $Z_D$ tiến hành như sau. Nó duyệt qua (theo một cách có hệ thống) tất cả các ID $I'$ của $Z_N$ và với mỗi $I'$, kiểm tra xem có một tính toán gồm không quá $2^{m-1}$ bước từ I đến $I'$, và một tính toán gồm không quá $2^{m-1}$ bước từ $I'$ đến $I''$ hay không. $Z_D$ cần một thanh ghi để theo dõi $I'$, khiến nó còn lại $m - 1$ thanh ghi. Vì vậy $Z_D$ đã giảm nhiệm vụ mô phỏng $2^m$ chuyển động của $Z_N$ sử dụng m thanh ghi thành mô phỏng $2^{m-1}$ chuyển động của $Z_N$ sử dụng $m - 1$ thanh ghi. Sau đó $Z_D$ giảm mỗi tính toán gồm $2^{m-1}$ bước thành hai tính toán gồm $2^{m-2}$ bước. $Z_D$ tiếp tục giảm độ dài của các tính toán mà nó cần kiểm tra cho đến khi nó chỉ cần kiểm tra, với các ID thích hợp $I_1$ và $I_2$, liệu với đầu vào w, $Z_N$ có thể trong một bước đi từ $I_1$ đến $I_2$ hay không. Điều này nó có thể dễ dàng thực hiện bằng cách sử dụng không gian lưu trữ bằng không. Bây giờ nếu có bất kỳ tính toán chấp nhận nào của $Z_N$, thì có một tính toán chấp nhận trong $2^{c'L(n)}$ bước. Vì vậy $Z_D$ có thể mô phỏng tính toán này bằng cách sử dụng $c'L(n)$ thanh ghi hoặc khoảng $[L(n)]^2$ ô của băng lưu trữ.

The idea of the algorithm is as follows. $Z_D$ has the string w as input. In the course of the algorithm, $Z_D$ will consider two ID's I, $I''$ stored in particular registers. For a prechosen m, it will need to check if, with input w, $Z_N$ can in $2^m$ steps change its configuration from I to $I''$. Furthermore, $Z_D$ will have to perform this task using only m registers. $Z_D$ proceeds as follows. It runs through (in a systematic way) all ID's $I'$ of $Z_N$ and for each $I'$, checks to see if there is a computation of at most $2^{m-1}$ steps from I to $I'$, and a computation of at most $2^{m-1}$ steps from $I'$ to $I''$. $Z_D$ needs one register to keep track of the $I'$, leaving it with $m - 1$ registers. So $Z_D$ has reduced the task of simulating $2^m$ moves of $Z_N$ using m registers to simulating $2^{m-1}$ moves of $Z_N$ using $m - 1$ registers. $Z_D$ then reduces each computation of $2^{m-1}$ steps to two computations of $2^{m-2}$ steps. $Z_D$ continues to reduce the length of the computations it need check until it need only check, for appropriate ID's $I_1$ and $I_2$, whether, with input w, $Z_N$ can in one step go from $I_1$ to $I_2$. This it can easily do using zero storage. Now if there is any accepting computation of $Z_N$, then there is one which accepts in $2^{c'L(n)}$ steps. So $Z_D$ can simulate this computation using $c'L(n)$ registers or about $[L(n)]^2$ squares of storage tape.

Bây giờ chúng ta định nghĩa một số ký hiệu cho phát biểu hình thức của thuật toán. Vì các ID là các chuỗi trên một bảng chữ cái hữu hạn, $\Delta$, chúng có thể được xem như các số nguyên trong ký hiệu m-adic, trong đó m là số ký hiệu trong $\Delta$. Cụ thể hơn, nếu $\Delta = \{a_1, a_2, ..., a_m\}$ thì chuỗi $a_{i_k} a_{i_{k-1}} \cdots a_{i_0}$ sẽ biểu diễn số $\sum_{j=0}^k i_j m^j$. Chúng ta sẽ không phân biệt giữa một chuỗi và số mà nó biểu diễn.

We now define some notation for a formal statement of the algorithm. Since ID's are strings over a finite alphabet, $\Delta$, they may be considered to be integers in m-adic notation, where m is the number of symbols in $\Delta$. More precisely, if $\Delta = \{a_1, a_2, ..., a_m\}$ then the string $a_{i_k} a_{i_{k-1}} \cdots a_{i_0}$ will represent the number $\sum_{j=0}^k i_j m^j$. We will not distinguish between a string and the number it represents.

¹ Chuỗi $d_l d_{l-1} \cdots d_0$ trên bảng chữ cái {1, 2} là biểu diễn dyadic của số $\sum_{i=0}^l d_i 2^i$.

¹ The string $d_l d_{l-1} \cdots d_0$ over the alphabet {1, 2} is the dyadic representation of the number $\sum_{i=0}^l d_i 2^i$.

ĐỊNH NGHĨA. Nếu $I$ và $I'$ là các ID của $Z_N$ và nếu $Z_N$ có thể trong một bước, với đầu vào $w$, chuyển từ cấu hình $I$ sang cấu hình $I'$, hoặc nếu $I = I'$, thì ta sẽ viết $I \xrightarrow{w} I'$. Trong thuật toán, ta sẽ kiểm tra xem $I \xrightarrow{w} I'$ có đúng với các chuỗi tùy ý $I, I'$ trên $\Delta$ hay không. Nếu $I$ hoặc $I'$ không phải là một ID của $Z_N$, thì phép kiểm tra thất bại.

DEFINITION. If $I$ and $I'$ are ID's of $Z_N$ and if $Z_N$ can in one step, with input $w$, pass from configuration $I$ to configuration $I'$, or if $I = I'$, then we will write $I \xrightarrow{w} I'$. In the algorithm we will test if $I \xrightarrow{w} I'$ is true for arbitrary strings $I, I'$ over $\Delta$. If either $I$ or $I'$ is not an ID of $Z_N$, then the test fails.

Trong thuật toán sau, $x_i$ biểu thị nội dung của thanh ghi thứ $i$ và $T_i$ biểu thị nội dung của thẻ thứ $i$ $[1 \leq i \leq c'L(n) + 1]$. $Z_D$ có một chuỗi $w$ làm đầu vào và mọi tham chiếu đến các tính toán của $Z_N$ đều có nghĩa là các tính toán của $Z_N$ dưới đầu vào $w$ và trong đó phần không trắng của mỗi băng công việc luôn dài không quá $L(|w|)$ ô. Tại bất kỳ thời điểm nào trong tính toán của $Z_D$, nếu $T_i = 1$, thì tồn tại một tính toán của $Z_N$ từ ID bắt đầu đến $x_i$.

In the following algorithm, $x_i$ denotes the contents of the $i$-th register and $T_i$ denotes the contents of the $i$-th tag $[1 \leq i \leq c'L(n) + 1]$. $Z_D$ has a string $w$ as input and all references to computations of $Z_N$ mean computations of $Z_N$ under the input $w$ and in which the nonblank portion of each work tape remains at most $L(|w|)$ squares long. At any point in the computation of $Z_D$, if $T_i = 1$, then there is a computation of $Z_N$ from the start ID to $x_i$.

THUẬT TOÁN CHO MÁY $Z_D$

ALGORITHM FOR MACHINE $Z_D$

Tóm tắt ký hiệu

Summary of Notation

$w$ là chuỗi đầu vào. $n$ là độ dài của $w$. $r$ là số nguyên nhỏ nhất sao cho $r \geq c'L(n)$. $c'$ là số sao cho, với $w$ làm đầu vào, nếu $Z_N$ chấp nhận $w$ tại bất kỳ thời điểm nào, thì $Z_N$ chấp nhận $w$ trong $2^{c'L(n)}$ bước. $I_0$ là ID ban đầu của $Z_N$. $N$ là số nguyên lớn nhất có biểu diễn $m$-adic có thể được lưu trong một thanh ghi. $x_i$ là nội dung của thanh ghi thứ $i$. $T_i$ là nội dung của thẻ thứ $i$.

$w$ is the input string. $n$ is the length of $w$. $r$ is the least integer such that $r \geq c'L(n)$. $c'$ is such that, with $w$ as input, if $Z_N$ accepts $w$ at all, then $Z_N$ accepts $w$ in $2^{c'L(n)}$ steps. $I_0$ is the initial ID of $Z_N$. $N$ is the largest integer whose $m$-adic representation can be stored in a register. $x_i$ is the contents of the $i$-th register. $T_i$ is the contents of the $i$-th tag.

D0 (Khởi tạo). Tính $r$ và thiết lập $r + 1$ thanh ghi và thẻ. Với $i = 1, 2, ..., r$, đặt $x_i \leftarrow 1$ và $T_i \leftarrow 0$. Đặt $x_{r+1} \leftarrow I_0$ (ID ban đầu) và $T_{r+1} \leftarrow 1$.

D0 (Initialize). Compute $r$ and set up the $r + 1$ registers and tags. For $i = 1, 2, ..., r$ set $x_i \leftarrow 1$ and $T_i \leftarrow 0$. Set $x_{r+1} \leftarrow I_0$ (the initial ID) and $T_{r+1} \leftarrow 1$.

D1 (Kiểm tra). Nếu mỗi $T_i = 1$, chuyển đến D3. Ngược lại, đặt $j$ là chỉ số nhỏ nhất sao cho $T_j = 0$. Kiểm tra: Với một chỉ số $h$ nào đó, $T_h = 1$ và $x_h \xrightarrow{w} x_j$. Có: Chuyển đến D2. Không: Chuyển đến D3.

D1 (Test). If each $T_i = 1$, go to D3. Otherwise, let $j$ be the smallest index such that $T_j = 0$. Test: For some index $h$, $T_h = 1$ and $x_h \xrightarrow{w} x_j$. Yes: Go to D2. No: Go to D3.

D2 (Xóa bộ nhớ) ($j$ như trong D1). Nếu $x_j$ là một ID chấp nhận, ACCEPT. Ngược lại, đặt $T_j \leftarrow 1$ và với $i = 1, 2, ..., j - 1$ đặt $x_i \leftarrow 1$ và $T_i \leftarrow 0$. Chuyển đến D1.

D2 (Clear Storage) ($j$ as in D1). If $x_j$ is an accepting ID, ACCEPT. Otherwise, set $T_j \leftarrow 1$ and for $i = 1, 2, ..., j - 1$ set $x_i \leftarrow 1$ and $T_i \leftarrow 0$. Go to D1.

D3 (Quay lui). Nếu $x_i = N$ với mỗi $i \leq r$, REJECT. Ngược lại, đặt $k$ là chỉ số nhỏ nhất sao cho $x_k \neq N$. Đặt $x_k \leftarrow x_k + 1$, $T_k \leftarrow 0$, và với $i = 1, 2, ..., k - 1$ đặt $x_i \leftarrow 1$, $T_i \leftarrow 0$. Chuyển đến D1.

D3 (Back Track). If $x_i = N$ for each $i \leq r$, REJECT. Otherwise, let $k$ be the smallest index such that $x_k \neq N$. Set $x_k \leftarrow x_k + 1$, $T_k \leftarrow 0$, and for $i = 1, 2, ..., k - 1$ set $x_i \leftarrow 1$, $T_i \leftarrow 0$. Go to D1.

Rõ ràng thuật toán hoạt động với bộ nhớ $c''[L(n)]^2$, trong đó $c''$ là một hằng số chỉ phụ thuộc vào $Z_N$. Bằng các kỹ thuật chuẩn [3], hằng số này có thể được giảm xuống còn một. Một phép quy nạp đơn giản theo số bước đã hoàn thành cho thấy rằng nếu $Z_D$ chấp nhận một đầu vào $w$, thì máy không tất định $Z_N$ cũng chấp nhận. Vì vậy, chỉ cần chỉ ra rằng $Z_D$ chấp nhận mọi chuỗi mà $Z_N$ chấp nhận. Để chỉ ra điều này, chúng ta cần một số bổ đề sơ bộ. Các bổ đề dễ phát biểu hơn trong trường hợp máy không dừng khi nó chấp nhận. Vì vậy, giả sử D2 (Xóa bộ nhớ) đã được sửa đổi để bỏ dòng đầu tiên ("If $x_j$ is an accepting ID, ACCEPT"). Ta sẽ nói rằng $Z_D$ đang ở cấu hình

Clearly the algorithm works within storage $c''[L(n)]^2$, where $c''$ is a constant depending only on $Z_N$. By standard techniques [3] the constant can be reduced to one. A simple induction on the number of steps completed shows that if $Z_D$ accepts an input $w$, then the nondeterministic machine $Z_N$ does. Thus, it will suffice to show that $Z_D$ accepts all strings that $Z_N$ accepts. To show this, we need some preliminary lemmas. The lemmas are easier to state in case the machine does not stop when it accepts. So assume D2 (Clear Storage) has been modified to omit the first line ("If $x_j$ is an accepting ID, ACCEPT"). We shall say $Z_D$ is in configuration

nếu nó sắp thực thi D1, và nội dung của các thanh ghi và các thẻ lần lượt là $x_1, x_2, ..., x_{r+1}$ và $T_1, T_2, ..., T_{r+1}$.

if it is about to execute D1, and the contents of the registers and tags are, respectively, $x_1, x_2, ..., x_{r+1}$ and $T_1, T_2, ..., T_{r+1}$.

Bổ đề 1. (Đối với D2 đã sửa đổi). Với mỗi chỉ số $i (i = 1, 2, ..., r)$ và mỗi số nguyên $x$ ($x = 1, 2, ..., N$), nếu tại một thời điểm nào đó trong một phép tính của $Z_D$ cấu hình của $Z_D$ là

Lemma 1. (For modified D2). For each index $i (i = 1, 2, ..., r)$ and each integer $x$ ($x = 1, 2, ..., N$) if at some time in a computation of $Z_D$ the configuration of $Z_D$ is

với một số $x_{i+1}, x_{i+2}, ..., x_r$ và một số $T_{i+1}, T_{i+2}, ..., T_r$, thì tại một thời điểm sau đó cấu hình sẽ là

for some $x_{i+1}, x_{i+2}, ..., x_r$ and some $T_{i+1}, T_{i+2}, ..., T_r$, then at some later time the configuration will be

hoặc

or

trong đó $j$ là chỉ số nhỏ nhất trong (1) sao cho $j > i$ và $T_j = 0$. (Nếu không tồn tại $j$ như vậy, thì (2) xảy ra.)

where $j$ is the least index in (1) such that $j > i$ and $T_j = 0$. (If no such $j$ exists, then (2) happens.)

Thuật toán đang cố gắng thiết lập rằng tồn tại một phép tính của $Z_N$ từ ID ban đầu đến $x_j$. Nó cố gắng thực hiện điều này bằng cách chỉ sử dụng các thanh ghi ở bên trái của $x_j$. Vì vậy, bổ đề nói rằng $Z_D$ có thể đưa bất kỳ ID nào vào bất kỳ thanh ghi nào, nếu cần.

The algorithm is trying to establish that there is a computation of $Z_N$ from the start ID to $x_j$. It is trying to do this using only registers to the left of $x_j$. So the lemma says that $Z_D$ can get any ID into any register, if it needs to.

Chứng minh. Một chứng minh hình thức sẽ sử dụng quy nạp trên $i$ và $x$. Chúng tôi liệt kê một số cấu hình tiêu biểu trong một tính toán. Điều này sẽ làm rõ bổ đề. Lưu ý rằng vì $N$ là một chuỗi mà tất cả các chữ số của nó đều giống nhau, $N$ không phải là một ID và do đó, $x \uparrow_w N$ không đúng với bất kỳ số nguyên $x$ nào. Giả sử $Z_D$ được khởi động trong cấu hình (1) và tại không thời điểm nào sau đó $Z_D$ nhận các cấu hình (3). Khi đó $Z_D$ sẽ nhận các cấu hình sau:

Proof. A formal proof would use induction on $i$ and $x$. We list some representative configurations in a computation. This should make the lemma clear. Note that since $N$ is a string all of whose digits are the same, $N$ is not an ID and, hence, $x \uparrow_w N$ is not true for any integer $x$. Suppose $Z_D$ is started in configuration (1) and that at no later time does $Z_D$ assume configurations (3). $Z_D$ will then assume the following configurations:

trong đó $T_i = 0$ hoặc 1.

where $T_i = 0$ or 1.

Cuối cùng, thông qua D3, $Z_D$ nhận (2) như mong muốn.

Finally, via D3, $Z_D$ assumes (2) as desired.

Bổ đề 2. (Đối với D2 đã sửa đổi). Giả sử tại một thời điểm nào đó trong một tính toán, cấu hình của $Z_D$ là

Lemma 2. (For modified D2). Suppose that at some time in a computation the configuration of $Z_D$ is

với $T_j = 0$ và các giá trị bất kỳ cho các $x$ và các $T$ còn lại. Nếu với một chỉ số nào đó $q, T_q = 1$ và có một tính toán của $Z_N$ gồm không quá $2^j$ bước từ $x_q$ đến $x$, thì tại một thời điểm sau đó cấu hình của $Z_D$ sẽ là (4) với $T_j = 1$.

with $T_j = 0$ and any values for the $x$'s and remaining $T$'s. If for some index $q, T_q = 1$ and there is a computation of $Z_N$ of at most $2^j$ steps from $x_q$ to $x$, then at some later time the configuration of $Z_D$ will be (4) with $T_j = 1$.

Bổ đề phát biểu rằng $j$ thanh ghi là đủ để $Z_D$ kiểm tra một tính toán gồm $2^j$ bước của $Z_N$.

The lemma says that $j$ registers are sufficient for $Z_D$ to check a computation of $2^j$ steps of $Z_N$.

Bổ đề 3. (Đối với D2 đã sửa đổi). Giả sử tại một thời điểm nào đó trong một tính toán, cấu hình của $Z_D$ là

Lemma 3. (For modified D2). Suppose that at some time in a computation the configuration of $Z_D$ is

với các giá trị bất kỳ của các $x$ và $T$. Nếu với một chỉ số nào đó $q, T_q = 1$ và có một tính toán của $Z_N$ gồm không quá $2^j$ bước từ $x_q$ đến $x$, thì tại một thời điểm sau đó cấu hình của $Z_D$ sẽ là

for any values of the $x$'s and $T$'s. If for some index $q, T_q = 1$ and there is a computation of $Z_N$ of at most $2^j$ steps from $x_q$ to $x$, then at some later time the configuration of $Z_D$ will be