A stream s is an infinite length sequence of symbols from finite alphabet £, that is, s
where si € E for all ¿ € N. Define a stream-language L to be a set of streams. A stream-TM M
9+, 90, I, £,8) is an ordinary TM with a special state q+ whose input tape takes an input stream
instead of an input string and M never halts. (Think perpetual machines from the practice final, but
Copyright By PowCoder代写 加微信 powcoder
the input is now infinite length.) We say that a stream-TM M decides a stream-language L if both the
following conditions hold
(1) For every stream s € L, M reaches g infinitely many times while running on input stream s.
(2) For every streams 7 L, M reaches q+ finitely many times while running on input stream s.
a) (10 points) Consider a binary alphabet £
= {0,1}. Prove that stream-language
divergent = (s : Vi E N, In > i, Sm ‡ sn+1}
is decidable by a stream-TM.
b) (15 points) Call a streams € {0, 1}∞ a rational stream if there exists strings p, 2 € {0, 1}* such that
= pa% (recall, strings are always of finite length). That is, s has p as a prefix and then repeats
a infinitely. Call s an irrational stream if it is not a rational stream. Prove that the language of
irrational streams
irrational = {s € {0, 1}°0: Vp, 2 € {0,1}*, s ‡ pa, 00}
is decidable by a stream-TM.
c) (Extra credit 30 points) Consider a binary alphabet £ = {0, 1}.
Prove OR Disprove: The stream-language
convergent = {s : In E N, Vi ≥ n, Si = Si+1}
is decidable by a stream-TM.
Hint: Consider the fact that the stream 0011001100110011… # Iconvergent so any decider for Iconvergent
must not enter a+ an infinite number of times on this stream. Please keep in mind that the Extra
Credit will be graded more harshly than other problems.
For all parts, remember to first write your intuition before writing your formal solution.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com