Ktl-icon-tai-lieu

RAM Programs, Turing Machines, and the Partial Recursive Functions

Được đăng lên bởi Kim Ngan
Số trang: 30 trang   |   Lượt xem: 1478 lần   |   Lượt tải: 0 lần
Chapter 4
RAM Programs, Turing Machines,
and the Partial Recursive Functions
4.1

Partial Functions and RAM Programs

We define an abstract machine model for computing functions
f : Σ∗ × · · · × Σ∗ → Σ∗ ,
n

where Σ = {a1 , . . . , ak } is some input alphabet. Numerical functions f : Nn →
N can be viewed as functions defined over the one-letter alphabet {a1 }, using
the bijection m → am
1 .
Let us recall the definition of a partial function.

279

280

CHAPTER 4. RAM PROGRAMS, TURING MACHINES

A binary relation R ⊆ A × B between two sets A and B is functional iff, for
all x ∈ A, and y, z ∈ B,
(x, y) ∈ R and (x, z) ∈ R implies that y = z.

A partial function is a triple f = A, G, B , where A and B are arbitrary sets
(possibly empty) and G is a functional relation (possibly empty) between A
and B, called the graph of f .
Hence, a partial function is a functional relation such that every argument
has at most one image under f .
The graph of a function f is denoted as graph(f ). When no confusion can
arise, a function f and its graph are usually identified.
A partial function f = A, G, B is often denoted as f : A → B.

4.1. PARTIAL FUNCTIONS AND RAM PROGRAMS

281

The domain dom(f ) of a partial function f = A, G, B is the set
dom(f ) = {x ∈ A | ∃y ∈ B, (x, y) ∈ G}.
For every element x ∈ dom(f ), the unique element y ∈ B such that (x, y) ∈
graph(f ) is denoted as f (x). We say that f (x) converges, also denoted as
f (x) ↓.
If x ∈ A and x ∈
/ dom(f ), we say that f (x) diverges, also denoted as f (x) ↑.
Intuitively, if a function is partial, it does not return any output for any input
not in its domain. This corresponds to an infinite computation.
A partial function f : A → B is a total function iff dom(f ) = A. It is customary to call a total function simply a function.

282

CHAPTER 4. RAM PROGRAMS, TURING MACHINES

We now define a model of computation know as the RAM programs, or Post
machines. RAM programs are written in a sort of assembly language involving simple instructions manipulating strings stored into registers.
Every RAM program uses a fixed and finite number of registers denoted as
R1, . . . , Rp, with no limitation on the size of strings held in the registers.
RAM programs can be defined either in flowchart form or in linear form.
Since the linear form is more convenient for coding purposes, we present
RAM programs in linear form.
A RAM program P (in linear form) consists of a finite sequence of instructions
using a finite number of registers R1, . . . , R...
Chapter 4
RAM Programs, Turing Machines,
and the Partial Recursive Functions
4.1 Partial Functions and RAM Programs
We define an abstract machine model for computing functions
f
×···×Σ

n
Σ
,
where Σ = {a
1
,...,a
k
} is some input alphabet. Numerical functions f: N
n
N can be viewed as functions defined over the one-letter alphabet {a
1
},using
the bijection m → a
m
1
.
Let us recall the definition of a partial function.
279
RAM Programs, Turing Machines, and the Partial Recursive Functions - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
RAM Programs, Turing Machines, and the Partial Recursive Functions - Người đăng: Kim Ngan
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
30 Vietnamese
RAM Programs, Turing Machines, and the Partial Recursive Functions 9 10 416