机器学习代写 | CSC 463H1 Assignment # 1

这个作业是完成机器学习理论相关的问题
CSC 463H1
Assignment # 1

1. [20 marks]
Show that the following functions are computable:
(a) f (x) = 3x
(b) f (x,y) = (
1 if x > y
0 otherwise.
You can assume the input numbers are in unary, and for part (b), the input is given as x$y.
2. [20 marks]
A Turing machine with left reset is a Turing machine with the following transition function:
δ : Q × Γ → Q × Γ × {R,RESET }.
If δ(q,a) = (q
0
,b,RESET ), then the Turing machine replaces a with b at its current tape position,
moves the tape head to the leftmost position on the tape, and transitions from state q to state q
0
.
Show that the set of languages recognized by the class of Turing machines with left reset is the same
as the set of languages recognized by the class of standard Turing machines.
3. [20 marks]
Prove that a language A ⊆ Σ
∗
is semi-decidable if and only if there is a decidable binary relation
R ⊆ Σ
∗ ×Σ
∗
such that for all x ∈ Σ
∗
,
x ∈ A if and only if there is some y ∈ Σ
∗
for which (x,y) ∈ R.
Recall that a binary relation R is decidable if there is a Turing machine M that determines in finite
time whether or not (x,y) ∈ R for a given pair (x,y) ∈ Σ
∗ ×Σ
∗
.
4. [20 marks]
Show that a language L is decidable if and only if there is some enumerator E that prints the strings
of L in lexicographic order.