Question

Hello I have an automata question could you help me?

[1Points] Give a formal description of a Turing Machine M  that takes two parameters: an integer and an array of integers and decides whether the given integer is an
element of the array or not. You can assume that all the integers are between 0 and 9. The input string will be written on the tape of the Turing machine. The first square
of the tape contains the integer, the second square of the tape has the #  symbol, and the next n squares of the tape have the elements of the array. Your Turing machine
should accept the input string if the integer (written in the first square of the tape) is an element of the array, and it should reject otherwise. The array is NOT sorted.

[1 Point s] What is the worst case asymptotic time complexity of your algorithm? You should use almost everywhere analysis. Present your result in notation and justify
your answer.

[1 Point s] Let us now assume that the array given as the parameter is sorted. From the introduction to programming classes, you know that we can decide whether a given
integer is an element of a given sorted array or not in time ) in modern computers, where n is the size of the array, by using the binary search algorithm. Is it possible to give a Turing Machine that solves the search problem on a sorted array in time?

O(logn

Answer 1

Basic idea: Construct a small WB program for each state that simulates that state. ● Combine all programs together to get an overall WB program that simulates the Turing machine. A State in a Turing Machine ● There are three kinds of states in a Turing machine: ● Accepting states, ● Rejecting states, and ● “Working” states. ● We can easily build WB programs for the first two: // qacc 0: Accept // qrej 0: Reject Working States ● At a given working state in a Turing machine, we will do exactly the following, in this order: ● Read the current symbol. ● Write back a new symbol based on this choice of symbol. ● Transition to some destination state. ● (Infinitely long) Tape of 1’s and 0’s • Able to read and write the tape, and move the tape • Has initial state, instructions, halt state • Instructions define for each state and value: – What value to write? – Whether the tape should be moved, and in which direction?

M - Turing Machine (The program) ∑ - Alphabet of Turing Machine x - String at which M begins (Input) Turing Machines M - Turing Machine (The program) ∑ - Alphabet of Turing Machine x - String at which M begins (Input) y – String at which M halts (Output) Turing Machines M - Turing Machine (The program) ∑ - Alphabet of Turing Machine x - String at which M begins (Input) y – String at which M halts (Output) I.e. for each value of x, M computes a function such that: Turing Machines M - Turing Machine (The program) ∑ - Alphabet of Turing Machine x - String at which M begins (Input) y – String at which M halts (Output) I.e. for each value of x, M computes a function such that: f:∑*  ∑*

TIME COMPLEXITY:

Each program has a maximum runtime • The worst-case time complexity of an algorithm on an input of size n – maximum time taken Big-O Notation • Each program has a maximum runtime • The worst-case time complexity of an algorithm on an input of size n – maximum time taken • Big-O notation ignores exact runtimes for simplification Big-O Notation • Each program has a maximum runtime • The worst-case time complexity of an algorithm on an input of size n – maximum time taken • Big-O notation ignores exact runtimes for simplification • E.g. (7.25n^2 – 1.14n + 2.83)/2  O(n^2)