Cpt S 516 Homework # 3
A computable function y = f(x) is one that can be implemented as a C
program that takes input x and halts with output y. The C program must
halt on any input.
1. (standard, 10pt) Show that if f(x, y) is a computable function, then so is
f(f(x, y), y).
2. (standard, 10pt) Let f(x) be a totally computable function. Define g as
follows:
g(0) = 1;
g(n+ 1) = f(g(n)).
Show that g is also a totally computable function.
3. (standard, 10pt) A word is a double word if it is in the form of ww for
some w. Let L be a recursive language. Let N be natural numbers. Define
a function f : N → N such that, for each n ∈ N , if there is a double word
in L of length n, then f(n) = 1, else f(n) = 0. Show that f is a totally
computable function.
4. (a little tricky, 10pt) A word is a double word if it is in the form of ww
for some w. Let L be a regular language. Let N be natural numbers. Define
a function f : N → N such that, for each n ∈ N , if there is a double word
in L of length ≥ n, then f(n) = 1, else f(n) = 0. Show that f is a totally
computable function.
5. (not hard, 10pt) Let F (x, y, z, x′, y′, z′) be any Presburger formula over
six free variables. Define G(n, x, y, z, x′, y′, z′) be a formula in the following
form:
∃x1, · · · , xn−1, y1, · · · , yn−1, z1, · · · , zn−1.
F (x, y, z, x1, y1, z1)∧F (x1, y1, z1, x2, y2, z2)∧· · ·∧F (xn−1, yn−1, zn−1, x′, y′, z′).
We say that F terminates iff ∃n.G(n, 0, 0, 0, 1, 1, 1) holds. Show that it is
undecidable whether F terminates. (From this result, one can show that G
is not Presburger)
1
6. (not hard, 10pt) Let n be a natural number. A linear function is a total
function f : Zn → Z (Z denotes the integers) such that there is a Presburger
formula F satisfying for all x1, · · · , xn, y ∈ Z,
F (x1, · · · , xn, y) holds iff f(x1, · · · , xn) = y.
A LP problem is defined as below.
Given: a number n, a linear function f , and a Presburger formula C(x1, · · · , xn).
Question: Is there a number K (< +∞) such that (1). for all x1, · · · , xn ∈
Z, K ≥ f(x1, · · · , xn), and (2). for some x1, · · · , xn ∈ Z, K = f(x1, · · · , xn).
Show that the LP problem is decidable.
7. (hard, 20pt) We use x and its subscripts x1, x2, · · · to denote integer
variables. A linear constraint is a formula in the following form:∑
1≤i≤n
aixi > a
where n is a natural number and the a’s are integers. A mod constraint is a
formula in the following form:
x mod a = b
where a 6= 0 and b are integers. A linear formula F is defined by the following
grammar:
F ::= C|F ∧ F |¬F
where C is a linear constraint or a mod constraint. Clearly (why?), a linear
formula is also a Presburger formula. We say that F is a linear formula over
x1, · · · , xn if x1, · · · , xn are all the integer variables appearing in F . Show
that for any Presburger formula P (x1, · · · , xn) over free variables x1, · · · , xn,
there is a linear formula F over x1, · · · , xn such that
for all integers x1, · · · , xn, P (x1, · · · , xn) holds iff F (x1, · · · , xn) holds.
8. (10pt, hard) I have four fish tanks: T1, T2, T3, T4, to hold water only (no
fish). The four tanks are identical. A water-level-test is one of the following:
WaterLevel(i) < 1?,
WaterLevel(i) = 1?,
WaterLevel(i) > 1?,
2
WaterLevel(i) < 2?,
WaterLevel(i) = 2?,
WaterLevel(i) > 2?,
where i = 1, 2, 3, 4. The test will tell whether the water level of tank Ti is
lower than 1, exactly 1, higher than 1, lower than 2, exactly 2, and higher
than 2. I also have a pump, which is controlled by pump-commands Θ in
the following form:
(θ1, θ2, θ3, θ4)
where each θi ∈ {in, stay, out}. The semantics of the pump-command is
straightforward. For instance, for the pump-command Θ = (in, out, stay, in),
I will pump q amount of water into the tank T1, pump q amount of water out
of the tank T2, do nothing to the tank T3, and pump q amount of water into
the tank T4, for some positive real number q (this number q is not specified
in the command. You can understand this q as a guessed number).
Let G = (V,E) be a directed graph, where V is a finite set of nodes, and
E ⊆ V × V be the set of (directed) edges (arcs). In particular, we identify a
node as the initial node, and a node as the final node. Further, we decorate
each edge with a water-level-test or a pump-command. The result is called
a decorated graph (we still use G to denote it). The semantics of a decorated
graph is also straightforward. Initially, the water level of all the four tanks
is exactly 1. It executes from the initial node then walks along the graph. G
can walk an edge (v, v′) if all of the following conditions are satisfied:
• if the edge is decorated with a water-level-test, I will actually perform
the test and make sure that the test returns true;
• if the edge is decorated with a pump command, I will actually perform
the command. We further require that, whenever the water level in
any tank reaches below 1 or above 2, all the tanks crash.
If at a node, G has more than one edge that can be walked, then G nondeter-
ministically chooses one. If at a node G has no edge that can be walked, then
G crashes (i.e., do not walk any further). We say that a decorated graph G
is terminating if G can walk from an initial node to a final node while the
tanks do not crash. Show that it is undecidable whether G is terminating.
9. (10pt, not hard) Let (A;A1, ..., Ar) be a system of finite automataA1, · · · , Ar
and a PDA A. They all share the same input alphabet Σ. Assume that
3
each finite automaton in the system starts in its initial state. We say that
a word w = a1a2...an is distributed-able if there is an assignment of each
symbol ai to one of the A1, ..., Ar such that if the subsequence of symbols
assigned to Ai is wi, then wi is accepted by Ai (for 1 ≤ i ≤ r). We say that
the system (A;A1, ..., Ar) is distributed-able if every word w accepted by A
is distributed-able. Provide an algorithm to decide whether the system is
distributed-able.
10. (10pt, Research) A thread system T is specified by a tuple
(C,Γ, R, c0, θ0)
where C is a finite set of colors with c0 being the initial color, Γ is a finite
set of signals with θ0 being the initial signal, and R is a finite set of rules.
Each rule is in one of the following two forms: θ, a → θ′, bc and θ, a → Λ,
where a, b, c are colors in C, θ, θ′ are signals in Γ and Λ is the empty string.
A (θ, a)-rule in R is a rule in the form of θ, a→ θ′, bc, or θ, a→ Λ, for some
b, c ∈ C and θ′ ∈ Γ. We say that a is θ-enabled if there is a (θ, a)-rule in R.
The semantics of T is as follows. When T runs, T keeps a multiset S of
objects, each of which is with a unique color, and a set Θ of signals. The
pair (S,Θ) is called a configuration. We say that an object is enabled under
configuration (S,Θ) if there is a signal θ ∈ Θ such that the color of the object
is θ-enabled. T starts with the initial configuration in which there is only
one object with color c0 and there is only signal θ0. Suppose that, currently,
the configuration of of T is (S,Θ). After a parallel move, the configuration
changes to (S ′,Θ′) as follows. That is, at the beginning of the parallel move,
S ′ and Θ′ are both empty. We say that a is enabled under (S,Θ) if there is
some θ ∈ Θ such that a is θ-enabled. Then, for each object o in S, (we use
a to denote the color of the o), if a is enabled under configuration (S,Θ),
then we nondeterministically pick a (θ, a)-rule, with θ ∈ Θ from R and do
the following:
• if the rule is θ, a → θ′, bc for some b, c ∈ C and θ′ ∈ Γ, then we put a
copy of a b-object and a copy of a c-object in S ′, and let Θ′ := Θ′∪{θ′};
• if the rule is θ, a→ Λ, then we do nothing.
If, however, a is not enabled under configuration (S,Θ), then we put a copy
of an a-object in S ′. We use (S,Θ) →T (S ′,Θ′) to denote such a parallel
4
move. In particular, we say that (S,Θ) is halting if it does not contain any
enabled objects. Clearly, when this is the case, S ′ = S and Θ′ = ∅.
An execution of T is a sequence
(S0,Θ0)→T (S1,Θ1) · · · →T (Sn,Θn)
for some n such that (S0,Θ0) is the initial configuration. An ω-execution of
T is a sequence
(S0,Θ0)→T (S1,Θ1) · · · →T (Sn,Θn) · · ·
such that each of its prefix is an execution. The ω-execution is bounded if
every (Si,Θi) is not halting and maxi≥0 |Si| <∞. (We use |S| to denote the
number of objects in a multiset S.) We say that T is bounded if T has a
bounded ω-execution.
Do you have an algorithm to decide whether T is bounded?
5

欢迎咨询51作业君