Martinakom

Not Rated (0)

$12/per page/Negotiable

About Martinakom

Levels Tought:
Elementary,Middle School,High School,College,University,PHD

Expertise:
Accounting,Applied Sciences See all
Accounting,Applied Sciences,Architecture and Design,Biology,Business & Finance,Calculus,Chemistry,Computer Science,Geology Hide all
Teaching Since: Jul 2017
Last Sign in: 398 Weeks Ago, 4 Days Ago
Questions Answered: 5023
Tutorials Posted: 5024
Category > Math Posted 20 Aug 2017 My Price 10.00

concat(u,v)=uv f(u)=uuu=concat(concat(u,u),u).

Hi! Need help with the attached question. I've also attached another file for reference and example.

Chapter 5
RAM Programs, Turing Machines,
and the Partial Recursive Functions
5.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. 369 370 CHAPTER 5. 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. 5.1. PARTIAL FUNCTIONS AND RAM PROGRAMS 371 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. 372 CHAPTER 5. 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.

Attachments:

Answers

Martinakom
Not Rated (0)
Status NEW Posted 20 Aug 2017 04:08 PM My Price 10.00

Hel-----------lo -----------Sir-----------/Ma-----------dam----------- Â-----------  -----------Tha-----------nk -----------you----------- fo-----------r y-----------our----------- in-----------ter-----------est----------- an-----------d b-----------uyi-----------ng -----------my -----------pos-----------ted----------- so-----------lut-----------ion-----------. P-----------lea-----------se -----------pin-----------g m-----------e o-----------n c-----------hat----------- I -----------am -----------onl-----------ine----------- or----------- in-----------box----------- me----------- a -----------mes-----------sag-----------e I----------- wi-----------ll -----------be -----------qui-----------ckl-----------y

Not Rated(0)