search
Log In

Recent questions tagged turing-machine

0 votes
0 answers
2
The Big Computer Corp. has decided to bolster its sagging market share by manufacturing a high-tech version of the Turing machine called, $BWTM$ that is equipped with bells and whistles. The $BWTM$ is basically the same as your ordinary Turing machine, except that each state of ... just entered. Prove that it is undecidable whether a given $BWTM \ M$, on given input $w$, ever blows the whistle.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 36 views
0 votes
0 answers
3
0 votes
0 answers
4
Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10^{i_{1}}10^{i_{2}}1\cdot\cdot\cdot$ ... be simulated for at least $s$ steps, then we shall eventually discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 34 views
0 votes
0 answers
5
In the box "Why 'Recursive'?" in Section $9.2.1$ we suggested that there was a notion of "recursive function" that competed with the Turing machine as a model for what can be computed. In this exercise, we shall explore an example of the recursive-function notation. A recursive function is a ... $A(2,1).$ What function of $x$ is $A(x,2)$? Evaluate $A(4,3)$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 61 views
0 votes
0 answers
6
We have considered only Turing machines that have input alphabet $\left\{0,1\right\}$. Suppose that we wanted to assign an integer to all Turing machines, regardless of their input alphabet. That is not quite possible because while the names of the states or noninput tape ... chosen. Show how we could assign an integer to all $TM's$ that had a finite subset of these symbols as its input alphabet.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 18 views
0 votes
0 answers
7
Here are two definitions of languages that are similar to the definition of $L_{d}$, yet different from that language. For each, show that the language is not accepted by a Turing machine, using a diagonalization-type argument. Note that you cannot develop an argument based on the diagonal itself, ... not accepted by $M_{2i}$. The set of all $w_{i}$ such that $w_{2i}$ is not accepted by $M_{i}$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 48 views
0 votes
0 answers
9
The purpose of this exercise is to show that a one-stack machine with an endmarker on the input has no more power than a deterministic $PDA$. $L\$ is the concatenation of language $L$ with the language containing only the one string $\$; that is, $L\$ is the set of all strings $w\$ such ... is the set of states $q$ such that $P$,started in $ID\ (q,a,X_{i}X_{i+1}\cdot \cdot X_{n})$ will accept.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 13 views
0 votes
0 answers
10
Informally but clearly describe counter machines that accept the following languages. In each case, use as few counters as possible,but not more than two counters. $\left\{0^{n}1^{m} \mid n\geq m\geq 1\right\}.$ $\left\{0^{n}1^{m} \mid m\geq n\geq 1\right\}.$ $\left\{a^{i}b^{j}c^{k} \mid i=j \text{or} i=k\right\}.$ $\left\{a^{i}b^{j}c^{k} \mid i=j \ \text{or} \ i=k \ \text{or}\ j=k\right\}.$
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 22 views
0 votes
0 answers
11
A two-dimensional Turing machine has the usual finite-state control but a tape that is a two-dimensional grid of cells, infinite in all directions. The input is placed on one row of the grid, with the head at the left end of the input and the control in ... state, also as usual. Prove that the languages accepted by two-dimensional Turing machines are the same as those accepted by ordinary $TM's$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 19 views
0 votes
0 answers
12
A $k$-head Turing machine has $k$ heads reading cells of one tape. A move of this $TM$ depends on the state and on the symbol scanned by each head. In one move, the $TM$ can change state, write a new symbol on the cell scanned by each head, and ... one that actually gets written there. Prove that the languages accepted by $k$-head Turing machines are the same as those accepted by ordinary $TM's$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 15 views
0 votes
0 answers
13
In Fig. $8.17$ we saw an example of the general simulation of a $k$-tape $TM$ by a one-tape $TM.$ Suppose this technique is used to simulate a $5$-tape $TM$ that had a tape alphabet of seven symbols. How many tape symbols would the one-tape $TM$ ... $TM$? Does it have any drawbacks compared with the other methods discussed?
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 13 views
0 votes
0 answers
14
In this exercise, we shall implement a stack using a special $3$-tape $TM$. The first tape will be used only to hold and read the input. The input alphabet consists of the symbol $\uparrow$ , which we shall interpret as "pop the stack," and the symbols $a$ ... $q_{f}$. Describe the transition function of the $TM$ informally but clearly. Also, give a summary of the purpose of each state you use.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 18 views
0 votes
0 answers
15
Design the following $2-$tape $TM$ to accept the language of all strings of $0's$ and $1's$ with an equal number of each. The first tape contains the input, and is scanned from left to right. The second tape is used to store the excess of $0's$ over $1's$ or vice - versa, in the part of the input seen so far. Specify the states, transitions, and the intuitive purpose of each state.
asked Jul 20, 2019 in Theory of Computation Lakshman Patel RJIT 22 views
0 votes
0 answers
16
Consider a nondeterministic $TM$ whose tape is infinite in both directions. At some time, the tape is completely blank, except for one cell, which holds the symbol $\$. The head is currently at some blank cell, and the state is $q.$ Write transitions that will enable the ... scanning the $\$. Suppose the $TM$ were deterministic instead. How would you enable it to find the $\$ and enter state $p?$
asked Jul 20, 2019 in Theory of Computation Lakshman Patel RJIT 34 views
0 votes
0 answers
17
Consider the nondeterministic Turing machine $M=\left(\left\{q_{0},q_{1},q_{2},q_{f}\right\},\left\{0,1 \right\},\left\{0,1,B \right\} ,\delta,q_{0},B,q_{f}\right)$ Informally but clearly describe the language $L(M)$ if $\delta$ ...
asked Jul 20, 2019 in Theory of Computation Lakshman Patel RJIT 22 views
0 votes
0 answers
18
Informally but clearly describe nondeterministic Turing machines $-$ multitape if you like $-$ that accept the following languages. Try to take advantage of nondeterminism to avoid iteration and save time in the non - deterministic sense. That is, prefer to have your $NTM$ branch a lot, while each branch ... form as $(b)$ but for at least two values of $j$, we have $w_{j}$ equal to $j$ in binary.
asked Jul 20, 2019 in Theory of Computation Lakshman Patel RJIT 22 views
0 votes
0 answers
19
Here is the transition function of a nondeterministic $TM \ \ M = \left(\left\{ q_{0},q_{1},q_{2}\right\},\left\{0,1\right\},\left\{0,1,B\right\},\delta,q_{0},B,\left\{q_{2}\right\} \right):$ Show the $ID's$ reachable from the initial $ID$ if the input is: $01$ $011$
asked Jul 20, 2019 in Theory of Computation Lakshman Patel RJIT 23 views
0 votes
1 answer
20
$L=\left \{< M_{1},M_{2}> \text{such that L}(M_{1})\prec L(M_{2}) \right \}$ is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \right )$ signifies language $L\left ( M_{1} \right )$ is reducible to $L\left ( M_{2} \right )$
asked Jul 15, 2019 in Theory of Computation ajaysoni1924 243 views
3 votes
1 answer
21
Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing machine $M$? $G$ is a CFG with $L(G)=\phi$ There exist two TMs $M_1$ and $M_2$ such that $L(M) \subseteq \{L(M_1) \cup L(M_2)\} = $ language of all TMs​​​​​. $M$ is a TM that accepts $\omega$ using at most $2^{\mid \omega \mid}$ cells of tape a and b only a only a, b and c c only
asked Jul 2, 2019 in Theory of Computation Arjun 476 views
1 vote
1 answer
22
For a statement A language $L \subseteq \Sigma^*$ is recursive if there exists some turing machine $M$. Which of the following conditions is satisfied for any string $\omega$? If $\omega \in L$, then $M$ accepts $\omega$ and $M$ ... $M$ halts without reaching to acceptable state If $\omega \in L$, then $M$ halts without reaching to an acceptable state
asked Jul 2, 2019 in Theory of Computation Arjun 584 views
0 votes
0 answers
23
How do a^n! and a^n^2 come under machine Linear Bound Automata? I know that LBA is a reduced form of standard Turing Machine where tape is restricted to be used for inputs(for also input of infinite length) But can anyone help me by designing a Turing Machine for a^n! or a ... number of states and a stack which may help for comparing any two of them only i.e, either for a & b or b&c or a&c).
asked Jun 12, 2019 in Theory of Computation Akash Kumar Roy 79 views
2 votes
1 answer
25
$P_{1}:$ {$<M>|M $ is a TM that accepts atleast $2$ strings of different length} $P_{2}:$ {$<M>|M $ is a TM and there exists an input whose length less than $100,$ on which $M$ halts } The number of problem which is $RE$ but not $REC$ _____________
asked Apr 30, 2019 in Theory of Computation srestha 271 views
0 votes
0 answers
26
$1)L=M$ is a turing machine $M$ accepts two strings of different length $2)L=M$ is a turing machine $M$ accepts atleast two strings of different length Which one RE? Which one REC? How to compute the different length string?
asked Apr 13, 2019 in Theory of Computation srestha 70 views
0 votes
0 answers
27
Design a subroutine to move a TM head from its current position to the right, skipping overall $0's,$ until reaching a $1$ or a blank. If the current position does not hold $0,$ then the TM should halt. You may assume that there are no tape symbols other than $0,1$ and $B$ ... use this subroutine to design a TM that accepts all strings of $0's$ and $1's$ that do not have two $1's$ in a row$.$
asked Apr 13, 2019 in Theory of Computation Lakshman Patel RJIT 84 views
0 votes
0 answers
28
A common operation in Turing-machine programs involves $"$shifting over$".$ Ideally, we would like to create an extra cell at the current head position, in which we could store some character. However, we cannot edit the tape in this way. Rather, we need to move ... position. Show how to perform this operation. Hint $:$ Leave a special symbol to mark the position to which the head must return.
asked Apr 13, 2019 in Theory of Computation Lakshman Patel RJIT 66 views
0 votes
0 answers
29
Design Turing machines for the following languages$:$ $\text{The set of strings with an equal number of 0's and 1's.}$ $\{a^{n}b^{n}c^{n}|n\geq 1\}.$ $\{ww^{R}|\text{w is any string of 0's and 1's\}}.$ Redesign your Turing machines from Exercise $8.2$ to take advantage of the programming techniques.
asked Apr 13, 2019 in Theory of Computation Lakshman Patel RJIT 52 views
0 votes
0 answers
30
Consider the Turing machine $M=(\{q_{0},q_{1},q_{2},q_{f}\},\{0,1\},\{0,1,B\},\delta,q_{0},B,\{q_{f}\})$ Informally but clearly describe the language $L(M)$ if $\delta$ consists of the following sets of rules$:$ ...
asked Apr 13, 2019 in Theory of Computation Lakshman Patel RJIT 61 views
...