2023年11月25日

代码代写｜COMP2181-WE01 Models of Computation

这是一篇英国的图灵机限时测试代码代写

 

Question 1

(a) Construct a Turing Machine that accepts well-formed arithmetic expressions over variables a, b and c with addition, +, multiplication, ×, and  brackets, ( and ).

There is no need to give the precise transition function – you could explain  how the machine works in plain English. You may use multiple tapes in  your machine.   [10 Marks]

(b) Describe a procedure that, for a given Turing Machine A, produces a (potentially infifinite) list of all words that are accepted by A, and nothing else.   [4 Marks]

(c) Suppose that you are given a Turing Machine A, whose language L (A) is infifinite. Describe a Turing Machine B that always terminates and decides an infifinite language L (B) which is a subset of L (A).   [6 Marks]

(d) For a fifixed tape language, e.g. {0, 1, t}, let f (n) be the maximum number of steps that any Turing Machine with n states makes before it terminates when ran on the empty input. Prove that the function f (n) is not computable.   [5 Marks]

Question 2

(a) Design a deterministic B¨uchi Automaton that recognises the language that  contains the infifinite binary words that start with a 1 and have non-empty fifinite segments of 0s of even length separated by single 1s.   [7 Marks]

(b) For an infifinite binary word, consider the sequence of the lengths of its alternating segments of 0s and 1s. For instance, the sequence for the word 0011101010001 . . . would be 2, 3, 1, 1, 1, 1, 3, . . . . Prove that the language consisting of all words for which this sequence is strictly increasing is not recognisable by any B¨uchi Automaton.    [10 Marks]

(c) Evaluate the Computation Tree Logic (CTL) formula A(q U EXp) on all states of the model below and show all your work.    [8 Marks]