New answers tagged

1

The easy and immediate way to see this is to note that the language of strings of length at most $k$ is finite, therefore it is regular. Regular languages are closed under complementation (just switch the accept and reject states), so your language of strings of length greater than $k$ is also regular.


0

Assume that the input is a valid description of a DFA $W$ (for any reasonable description this is a decidable problem). You need to show that, given $W$, is is possible to decide whether there exists a word $w \in \{b,c\}^*$ that is accepted by $W$. Since $W$ is a DFA, $L(W)$ is a regular language. By the closure properties of regular languages, $L' = L(W) \...


0

All finite languages are decidable.


-3

Turing machine is a machine and machine has some parts. Tape is one part of machine which executes operation of mathematical model for example computer is a machine which executes operations of Boolean model. All these models are logical in behaviour. We are thankful to the engineer who converted Boolean model to switching circuits.


3

Modern computers are not more powerful than a TM. The meaning/definition of "mechanical means" is not "a TM"; "mechanical means" refers to any step-by-step process that can be carried out in the real, physical world. For instance, it would include mechnical devices, electronic devices, a human following a procedure "...


2

The languages are not the same. In the first one, $w$ is a part of the input. In the second one, $w$ is fixed beforehand, and the language has to depend on what you fix it to be.


1

Informally, a pushdown automaton has a way to store and use an infinite amount of memory (the stack). In a Turing machine, the only way to store an infinite amount of memory is to write it on the tape. But in a Turing machine without return, you cannot go back to the cells that you have already written, so that memory can never be used. That means that a ...


1

The starting state must be different than the accepting state or you will end up accepting all words. As for an indication to solve your problem, you should consider multiple states of the Turing Machine: searching for a $0$ or a $1$; already encountered a $0$ (replaced with a special symbol $\\\$$), searching for a $1$ to replace it with $\\\$$; already ...


3

The problem is decidable. You can enumerate the (finitely many) programs that use at most $b$ bytes. For each such candidate program $P$, you can check whether $P$ is valid program (for any reasonable representation) and execute it for up to $t$ time steps. Eventually you either find a program that prints $s$ (and accept) or you run out of programs (and ...


7

I'm afraid that your logic doesn't make sense, since you can't implement Step 1. In order to implement it, you'll have to run $M$ and see if it every halts, but this is impossible, since it's the halting problem. Nevertheless, the problem is decidable. The details of this argument depend on the exact Turing machine model, but in order to illustrate the basic ...


0

I think your interpretation is correct. $q_i$ and $q_{ii}$ are states that guarantee that $10$ and $100$ will be correctly accepted. It is clear that any other input of size $\leq 3$ will be rejected. Now suppose you are in state $q_s$, the tape is $1Z^{2^k}u$ (with $u\in \{0,1\}^*$), and the head is in position of the first $Z$ of the tape. The cycle $q_s, ...


-1

Try to define $M'$ that would accept $\iff$ both $M_1$ and $M_2$ accepted or rejected (together)


0

Yes, the DFS is an algorithm, and hence has an equivalent turing machine. The definition of the decidability as you have said, is for the language to be exactly accepted by some turing machine. The formal definition of the turing machine accepting the language of strongly connected graphs probably is waaaay too hard to explicitly write, so I guess your ...


1

An LBA is limited to working only on the space defined by the input. That means it won't ever move right on reading a blank space (if your model doesn't allow writing blank, only a fake blank, that is). That is easy to check by looking at the transitions of the TM. To check if the language is accepted by an LBA is undecidable by Rice's theorem.


0

No, assume towards contradiction you would have been able to solve it, with some Turing machine $M$. Notice, that it's easy to check given an LBA whether it halts or not (there are a finite number of total possible states) and let's call a TM that solves this by $M'$. Now, let us construct the new Turing machine $\hat M$ that will solve the halting problem: ...


1

I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular, and regular languages are decidable by a TM. Does it make sense for answering the question? You can easily simulate any DFA in your model, and so your model ...


0

The definition of Turing reducible, is that there exists a Turing reduction - an algorithm for $A+B$ that uses an oracle to $A$. To understand this, you must first understand oracle machines. Those machines, are like turing machines, but can ask an "oracle" whether any $x$ is in $A$ or not, and would get an answer in $O(1)$, regardless of what $A$ ...


2

The intent of this assignment seems to be to demonstrate that allowing Turing Machines to treat the tape as infinite in both directions will not increase the computational power of the Turing Machine; in other words, that for any unbounded-tape TM, there exists an equivalent classical TM. This means you can't just "reject if we go too far to the left&...


1

The question is given you have an oracle machine/black box for HPC can you decide if <M,w1,w2,w3> is in LOOP. See the wikipedia page on that: https://en.m.wikipedia.org/wiki/Reduction_(recursion_theory)#Turing_reducibility The proof is very straightforward as you already know.


1

If $E_{DFA}$ with input $C$ accepts, then $C = L(M) \cap B = \emptyset$. In other words, no word containing an odd number of 1s is also in $L(M)$. Then, by definition of $A$ you should accept. Conversely, if $E_{DFA}$ with input $C$ rejects, then $C = L(M) \cap B \neq \emptyset$. That is, there is some word $w \in L(M)$ such that $w$ contains an odd number ...


1

The language $S = S_1 \circ S_2$ (I'm assuming that was the intended notation) is in NP if $S_1,S_2$ are in NP. Indeed, given verifiers for $S_1,S_2$, we can construct a non-deterministic verifier for $S$ as follows: Given an input $x \in \{0,1\}^*$, guess a decomposition $x = x_1 \ldots x_n$ for even $n$, and use the verifiers for $S_1,S_2$ to verify that $...


1

While a specific program could be self-delimiting, in this context what we usually mean is a self-delimiting encoding of programs. An encoding of programs is self-delimiting if it forms a prefix code, that is, no program is a prefix of another program. Intuitively, programs are self-delimiting, so there is no ambiguity in where a program ends. Why do we care?...


1

The Turing machine M is running the Turing machine E as its subroutine. In the other words, you can think of E's printer tape as another tape for Turing machine M. Although we don't know what is going on E, E's computation is part of (inside) M's computation. And of course, as nir shahr said in the comment, comparing is part of M's computation too. I drew ...


0

You are going to want to use a many-one reduction for this problem. Note that $ii \implies i$ so it is sufficient to prove statement $ii$. We know that the complement to the halting problem $$ \bar{H}=\{\langle M, w \rangle \mid M \text{ does not halt on }w\}$$ is not recursively enumerable. We can reduce $\bar{H}$ to $Language1$ $S$ = " $\quad$on ...


2

I claim that $L$ is decidable and I will construct a Turing machine to decide $L$. Let $M$="on input $\langle M' \rangle$ $\quad ACCEPT$ " Why does $M$ decide $L$? $M$ takes a description of a Turing machine as input and accepts, that is $L(M)=\{ \langle T \rangle \mid T \text{ is a Turing machine}\}$. If the input is not a description of a Turing ...


1

You want to show that this modified Turing machine is equivalent to the standard definition of a Turing machine, that is for every modified Turing machine $T'$ there exists a standard Turing machine $T$ such that $L(T')=L(T)$, and vice versa. It is easy to show that for every standard Turing machine $T$ there is a modified Turing machine which accepts $L(T)$,...


1

Let $L$ be a decidable language and let $M$ be a decider for $L$. Since $M$ decides $L$, $M$ always halts and accepts if its input is in $L$ and rejects if its input is not in $L$. We know that string reversal can be performed by a Turing machine. Let's construct a Turing machine to decide if a word is in $L^r=\{w=w_0w_1...w_n \mid w^r=w_nw_{n-1}...w_0\in L\}...


1

Suppose that you have a Turing machine $M$ that accepts a language $L$. Construct a new Turing machine which, on input $x$, reverses its input and then passes control to $M$. The new Turing machine accepts the reverse of $L$.


Top 50 recent answers are included