For a Turing machine M, (M) refers to the binary representation of M.For a Turing machine M, L(M) contains the set of all strings accepted by M.For a Turing machine M and an input x = {0,1}*, Steps(M, x) refers to the number of steps takenby M to execute on x before it halts. Here, one step of execution of M on x = one movement (left orright) of the tape head.For a Turing machine M and an input x = {0,1}*, we define the following:ReachCells(M,x) = {i : M reaches ith tape cell when M is executed on x}Informally, it contains all locations on the tape that are visited when M is ecuted on x. Theleftmost location on the tape is the first tape cell, the location next to it is the second tape cell, and soon.A string w₁ is an anagram of w2 if w₁ can be obtained by rearranging the alphabets of w2. Formally, ifw₁ is an n length string, wê is called an anagram of w₁ if there exists a permutation à on n elementssuch that π(w₁) = W2. Prove that the following language L is decidable:L = {(M) : 3x € L(M), Steps(M, x) ≤ 100}.

The Turing machineInformally, a Turing machine is a finite automaton equipped with unbounded memory.This memory is given in the form of one or more tapes, which are infinite in both directions.The tapes are divided into an infinite number of cells in both directions.Every tape has a distinct starting cell which we will also call the 0th cell.On every cell of every tape, a symbol from a finite alphabet can be written. With the exception of finitely manycells, this symbol must be a special symbol of the alphabet, denoting the “empty cell”.To access the information on the tapes, we supply each tape by a read-write head..At every step, this sits on a cell of the tape.The read-write heads are connected to a control unit, which is a finite automaton. Its possible states form a finite set Γ.There is a distinguished starting state “START” and a halting state “STOP”.Initially, the control unit is in the “START” state, and the heads sit on the starting cells of the tapes. In every step, each head reads the symbol in the given cell of the tape, and sends it to the control unit.Depending on these symbols and on its own state, the control unit carries out three things:it sends a symbol to each head to overwrite the symbol on the tape (in particular, it can give the direction to leave it unchanged);it sends one of the commands “MOVE RIGHT”, “MOVE LEFT” or “STAY” to each head;it makes a transition into a new state (this may be the same as the old one);The heads carry out the first two commands, which complete one step of the computation. The machine halts when the control unit reaches the “STOP” state.While the above informal description uses some engineering jargon, it is not difficult to translate it into purely mathematical terms. For our purposes, a Turing machine is completely specified by the following data:T = hk, Σ, Γ, α, β, γi, where k 1 is a natural number, and are finite sets, Σ, ST ART, ST OP ∈ Γ, and α, β, γ are arbitrary mappings:α :Γ × Σk → Γ, β :Γ × Σk → Σk,γ :Γ Σk → {−1, , 1}k..Here it specifies the new state, specifies the symbols to be written on the tape and γ specifies how the heads move.In what follows we fix the alphabet Σ and assume that it contains, besides the blank symbol ∗, at least two further symbols, say 0 and 1 (in most cases, it would be sufficient to confine ourselves to these two symbols).Under the input of a Turing machine, we mean the k words initially written on the tapes. We always assume that these are written on the tapes starting at the 0 field and the rest of the tape is empty ( is written on the othercells). Thus, the input of a k-tape Turing machine is an ordered k-tuple,each element of which is a word in Σ∗. Most frequently, we write a non-empty word only on the first tape for input. If we say that the input is the word x then we understand that the input is the k-tuple (x, , . . . , ∅).The output of the machine is an ordered k-tuple consisting of the wordson the tapes after the machine halts. Frequently, however, we are really interested only in one word, the rest is “garbage”. If we say that the output is a single word and don’t specify which, then we understand the word on the last tape.It is practical to assume that the input words do not contain the symbol ∗. Otherwise, it would not be possible to know where the end of the input is: asimple problem like “ﬁnd out the length of the input” would not be solvable: no matter how far the head has moved, it could not know whether the input has already ended. We denote the alphabet Σ \ {∗} by 0. (Another solution would be to reserve a symbol for signaling “end of input” instead.) We also assume that during its work, the Turing machine reads its whole input; with this, we exclude only trivial cases.Turing machines are defined in many diﬀerent, but from all important points of view equivalent, ways in different books.Often, tapes are infinite only in one direction; their number can virtually always be restricted to two and in many respects even to one; we could assume that besides the symbol ∗ (which in this case we identify with 0) the alphabet contains only the symbol 1; about some tapes, we could stipulate that the machine can only read from them or can only write onto them (but at least one tape must be both readable and writable) etc.The equivalence of these variants (from the point of view of the computations performable on them) can be verified with more or less work but without any greater difficulty and so is left as an exercise to the reader. In this direction, we will prove only as much as we need, but this should give us sufficient familiarity with the tools of such simulations.When we describe a Turing machine,we omit defining the functions at unimportant places, e.g., if the state is “STOP”.We can consider such machines as taking α = “STOP”, β = ∗k and γ = 0k at such undefined places. Moreover, if the head writes back the same symbol, then we omitgiving the value of β and similarly, if the control unit stays in the same state, we omit giving the value of γ.Complexity of Multi-Tape Turing MachinesGiven some multi-tape Turing machine M" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input error, we can build an equivalent single tape machine S" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input error is defined as follows:S=" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?=Math input errorMath input errorMath input errorMath input errorMath input error “On input w=w1w2...wn:" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?=?1?2...??:Math input errorMath input errorMath input errorMath input errorMath input errorPut the tape into the format described above:#w1˙w2...wn#⊔˙#⊔˙#⊔˙#⊔˙..." data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">#?1˙?2...??# #⊔˙#⊔˙#⊔˙...To simulate a single move, S" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">? scans the entire tape to see which symbols are under the tape heads (the dotted symbols). It then makes a second pass according to the transition function of M" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">? to change the tape: writing new symbols under the tape heads, and moving the dots left or right.How much computational complexity is introduced with this simulation? If the multi-tape Turing machine M" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error runs inComplexity of Turing MachinesNext, we’ll consider a non-deterministic Turing machine. We define the running time t(n)" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?(?)Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error of a non-deterministic Turing machine as the maximum number of steps in any branch of the computation: t(n)" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?(?)Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error time, how much time is required for the single-tape machine S" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error provided by this construction?Because S" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error must scan across the tape for each step of the computation, the time required is equal to the time required to scan the tape times the number of steps t(n)" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?(?)Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error.It may seem it takes O(n)" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">O(?)Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error time to scan the tape, but the operation of M" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error may be increasing the length of the tape as it runs. The maximum amount M" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error can increase the tape is k×t(n)" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?×?(?)Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error where k" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error is the number of tapes.Thus, the time to scan the tape is at most O(t(n))" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">O(?(?))Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error, and the full running time of S" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error is O(t2(n))" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">O(?2(?))Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error.By the definition of a non-deterministic Turing machine complexity, every branch of the tree has length at most t(n)" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?(?)Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error. Every node in the tree has at most b" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error children where b" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error is the maximum number of choices at any point in the N" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error.Thus, the total number of leaves in the tree is at most bt(n)" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">??(?)Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error. The number of nodes in the tree is less than twice the number of leaves. So we can bound it by O(bt(n))" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">O(??(?))Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error.The time it takes to travel from the root to any one node is O(t(n))" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">O(?(?))Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error. Thus the total running time of D" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error is O(t(n)bt(n))" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">?(?(?)??(?))Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error. This is equal to 2O(t(n))" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">2O(?(?))Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error.The simulation actually uses a three-tape Turing machine. As discussed above, this at most squares the running time, so we have (2O(t(n)))2=2O(2t(n))=2O(t(n))" data-mce-style="box-sizing: inherit; display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 18px; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;" data-mce-tabindex="0">(2O(?(?)))2=2O(2?(?))=2O(?(?))Math input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input errorMath input error.