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

机器学习代写 | 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.


程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持 Alipay WeChatPay PayPal等支付方式

E-mail: vipdue@outlook.com  微信号:vipnxx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank