10年专注于英语国家留学生作业代写,网课代修,网课Exam代考
数学Essay代写_数学作业代写_数学题代做_DueEssay论文代写

数学Essay代写_数学作业代写_数学题代做

北美数学代写:精英数学写手,数学题代做,数学代考 math代写/数学代写/算法代写/algorithm代写:这是一个数学代写,主要涉及非线性问题等基础数学问题, Dueessay 是一个专业留学生论文..

dueessaysanhao 立即咨询

快速申请办理

称       呼 :
联系方式 :
备       注:

数学Essay代写_数学作业代写_数学题代做

发布时间:2021-03-23 热度:

北美数学代写:精英数学写手,数学题代做,数学代考

math代写/数学代写/算法代写/algorithm代写:这是一个数学代写,主要涉及非线性问题等基础数学问题,唯一网址:www.mingxinwrite.com是一个专业留学生论文代写平台,在您对自己论文没有把握的时候,我们可以帮您完成高分论文,给您的顺利结束学业增光添彩,如果您有需求可以直接联系右边的客服,为您解答疑惑。



1. nLRA Problem (40 points)
Recall the definition of a Lovesick Robot Automaton (LRA). A Lovesick Robot Automaton is a type of
machine which takes a finite string as input, and generates an infinite pattern. We think of the LRA
as starting at position 1 on an infinite tape and moving right in a sequence of steps, and at each step
it decides to either mark the current cell on the tape with a ♥ or to not mark anything, i.e. it leaves a
blank character, which we denote with “ ”. The LRA has the following characteristics:
• Just as in the case of a DFA, a LRA is a five tuple (Q, Σ, δ, q0, F). However, after a LRA has processed
the last character of the input string, it goes back to the first character. So a LRA processes the
string repeatedly in an infinite loop. Each step of the robot corresponds to a state transition.
• The set F is now called the set of marking states. At each step, if the new state is a marking state
then the robot marks the new cell with a ♥. Otherwise, the robot does not make a mark in this
position, i.e. it leaves it blank ( )
• It is only after processing the first symbol of the input that the LRA either creates a mark ♥ or
leaves a blank , depending on what state the LRA enters after processing this first symbol.
Define a New Lovesick Robot Automaton (nLRA) to be an LRA which can decide at each step which
direction to move on the infinite tape. In other words, the transition function is now defined as δ :
Q × Σ → Q × {L, R}. If δ(q, a) = (q
0
, R) then the robot moves right on the tape and leaves a ♥ if q
0
is a
marking state. Likewise, if δ(q, a) = (q
0
, L) then the robot moves left on the tape and leaves a ♥ if q
0
is
a marking state. (If the robot is at position 1 and tries to move left then it just stays at position 1.)
We will explore the question of using a Turing Machine to decide questions about nLRAs. To that end,
denote by hhRii an encoding of an nLRA R.
(a) (20 points) Rigorously prove the following new “pumping lemma” for nLRAs:
Lemma 1. For any nLRA M and any string s, there exist w, z ∈ {L, R}

such that the pattern of
directions taken by the robot when executing M(s) is of the form wzzzzz . . . .
(b) (20 points) Show the language
L = {(hhRii, s) | For all n ∈ N, R(s) eventually visits the n-th cell on the infinite tape}
is decidable.
2. Libra Machines (85 points)
In this problem, we define a Turing machine variant called a Libra Machine (LM). A Libra Machine has
a total of three tapes: in addition to its regular tape, it has two machine tapes. The LM can write to
the three tapes in the ordinary way, but it has an extra trick up its sleeve. At any given moment, the
LM can go into a special query state and perform a language equality query. Suppose an ordinary Turing
Machine representation hM1i is stored on the first machine tape of an LM T, and another ordinary Turing
Machine representation hM2i is stored on the second machine tape of T. If T enters the query state, then
immediately T learns whether L(M1) = L(M2). In particular, if L(M1) = L(M2), then T enters a special
state called the yes state without consuming any input or moving the tape. If L(M1) 6= L(M2) then T
enters another special state called the no state. We say that a language L ⊆ Σ

is Libra recognizable
(respectively, Libra decidable) if there exists an LM T recognizing (respectively, deciding) L.
Note: Throughout this problem, hMi denotes a description of an ordinary Turing machine.
Example: A Libra machine can easily decide the language {(hM1i,hM2i) | L(M1) = L(M2)}. The
machine simple writes hM1i to the first machine tape and hM2i to the second tape and enters the query
state, and accepts if it enters the yes state.
(a) (15 points). Show that the language
HALT = {(hMi, x) | M halts on input x}
is Libra decidable.
(b) (20 points). Show that the language
MINIMAL = {hMi | M is a minimal turing machine}
is Libra decidable. (This language is defined in Section 6.1 in Sipser.)
(c) (20 points). Show that there exists a language L which is not Libra recognizable.
Hint: Think about infinities.
(d) (30 points). Show that there exists a language L which is Libra recognizable but not Libra decidable.
3. Decidability and Recognizability (90 points)
Consider the following language:
DISAGREE = {(hM1i,hM2i) | there exists an x such that x ∈ L(M1) but x 6∈ L(M2)}
(a) (15 points). Show DISAGREE is undecidable.
(b) (15 points). Show DISAGREE is unrecognizable.
Now we define a machine called a fibonacci enumerator. A two-tape Turing Machine is a fibonacci
enumerator if it runs forever and for any fibonacci number n, the binary representation of n is eventually
written to the work tape.
Consider the following language:
FIB = {hMi | M is a fibonacci enumerator}
(c) (25 points). Is FIB recognizable? Prove or disprove.
Finally, consider the language
SMALLANDPICKY = {(hMi, x) | M is a minimal Turing machine where L(M) = {x}}
(d) (10 points). Show that the set
{hMi | there is some x such that (hMi, x) ∈ SMALLANDPICKY}
is infinite.
(e) (25 points). Show that SMALLANDPICKY is unrecognizable.
4. Language Properties (40 points) In this problem we study variants of Rice’s theorem.
(a) (20 points). Define a strong nontrivial property of languages to be a nontrivial property of languages
P where P(∅) = 1. Show that for any such P the language
LP = {hMi | P(L(M)) = 1}
is unrecognizable.
(b) (20 points). Define a 2-dimensional nontrivial property of languages to be a function P : P(Σ∗
) ×
P(Σ∗
) → {0, 1}, such that the following property holds:
(i) There exist Turing Machines M, Myes, Mno where P(L(M), L(Myes)) = 1 but P(L(M), L(Mno)) =
0.
Show that for any such P, the language
LP = {(hM1i,hM2i) | P(L(M1), L(M2)) = 1}
is undecidable.
(c) (40 points extra credit). Now consider a variant of the previous problem where (i) is replaced by
the following:
(i) There exist Turing Machines M1, M2, M0
1
, M0
2 where P(L(M1), L(M2)) = 1 but P(L(M0
1
), L(M0
2
)) =
0.
Show that it is still the case that for any such P, the language LP is undecidable.


关闭窗口
上一篇:理学essay代写_数学essay代写
下一篇:专业论文代写指南_DueEssay高端数学论文作业代写

相关阅读

数学题代做,math代考,数学网课代考,北美数学作业代写
数学题代做,math代考,数学网课代考,北美数学作业代写

Mingxinwrite数学作业代写,多年从英国、加拿、澳洲、数学课程辅导, 数学代考 ,数学题代做, math代考 ,数学代做,美国数学代写, 留学生代写 ,微积分代写。 Mingxinwrite 拥有...

数学作业代写_数学代考_数学题代做
数学作业代写_数学代考_数学题代做

数学essay代写,数学网课代修,数学代考,各类数学作业代写,留学生math assignment代写, 数学题代做 ,math代考,数学网课代考,数学题代做。 数学作业代写介绍 Mingxinwrite专注提供专...

理学essay代写_数学essay代写
理学essay代写_数学essay代写

美国essay代写,加拿大essay代写,澳洲essay代写,哈佛代写essay,宾夕法尼亚代写essay 来自世界顶尖大学的专业本地写手根据您的要求帮助您各种essay代写修改。保证 100%原始和准...


代写
微信

微信客服

微信客服:dueessaysanhao

山东济南市历下区三庆财富中心

qq

QQ客服

QQ联系:3029629821