Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [turing-machines]

Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

1
vote
1answer
18 views

Is the set of context free grammars that generate all words in co-RE?

Is $\{\langle G \rangle | L(G) = \sum^{\star}\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.
1
vote
1answer
17 views

Reduce ATM to REGULAR_TM

Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$. Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\...
1
vote
1answer
19 views

Number of divisors of a number - in NP?

I'm trying to show that the language {(m,n)|m has exactly n divisors} is in NP. The input (m,n) is in binary. The non-deterministic Turing machine for the language would be: 1) Guess the prime ...
1
vote
0answers
11 views

What is the difference between the input set of a BSS RAM and a language?

I'm currently learning some things about BSS RAMs. For sake of simplicity, please imagine them as a Turing machine over the reals. Now, this machine gets some real numbers as input. The input values ...
-1
votes
0answers
12 views

Turing machine 2 input, word1 substring of word2!

I need a turing Machine with 2 input words, determine if word1 is substring of word2. Lenguage symbols(+ , - , r(return)) I don't know how can do that exercise, if anyone can help me please. Exemple:...
2
votes
2answers
30 views

Quotient in LOOP program

I want to construct a LOOP-computable program for the integer division (quotient): x = a DIV b The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language) I ...
0
votes
2answers
31 views

Halting problem of TM which recognize recursive languages is undecidable?

I am preparing for an exam and I came across this question in one of the tests. Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False) The solution ...
0
votes
1answer
19 views

Is this language recognizable?

Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable. I don't think it's even recognizable, but I'm not sure. Regardless, I ...
-1
votes
0answers
21 views

Given a State machine M, Express these in LTL

I got this question in my exam. Can someone explain, what will be the correct answer for this. Thanks in advance. Given the language of the question, will you consider this answer correct? (where i ...
-1
votes
0answers
15 views

Context free grammar to Turing Machine

I have the following problem: Draw the diagram of a TM for the language : of all binary strings of odd length with a 1 in the middle. My approach to this in CFG is as follows: ...
0
votes
0answers
15 views

Agree or Disagree the Strong AI Hypothesis [closed]

Do you agree or disagree the following statement: The "Strong AI Hypothesis" claims that it is possible to program a digital computer so that it embodies true human-like consciousness, i.e., ...
0
votes
0answers
8 views

Turing Machine question [closed]

If my TM accepts w- that means that ill get to a final state while processing w. Now if I want the TM to accept another word, z, that w is prefix of. How can I do so if delta function is defined only ...
0
votes
0answers
30 views

Turing machine, tape without blanks, does it halt or no?

So I'm lost on this one. We're given a turing machine and an initial tape. Tape is infinitely long in both ways, but all the blanks are taken out. The head is the leftmost nonblank. So the question is:...
0
votes
0answers
18 views

Is it possible to enumerate all strings of a Recursively Enumerable language (but non recursive) in some order?

In case of recursive languages, generate each string in some order (say alphabetically) and give it to respective TM, if it halts at a final state then string is present in language, otherwise not. ...
0
votes
1answer
30 views

What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA?

I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking ...
2
votes
1answer
27 views

Turing machine with semi infinite tape - Prove by construction

I'm studying constrained Turing Machines. There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 ...
0
votes
1answer
21 views

Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.

...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM. I had this problem on my exam. From my ...
0
votes
0answers
10 views

About a “modification” of the diagonal language $\{w_i \mid \text{Every turing machine } M_1 \ldots M_i \text{ reject } w_i\}$

I have given the seeming modification of the diagonal language $\{w_i \mid \text{Every turing machine } M_1 \ldots M_i \text{ rejects } w_i\}$, yet I can't prove that it is undecidable. My thoughts ...
0
votes
0answers
13 views

Whether language of all turing machines is decidable or undecidable or semi-decidable?

I recently came across this language: $L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$ It was asked in the question to find out whether language L is decidable or undecidable. ...
0
votes
0answers
25 views

What is the power of a Turing-machine that cannot write?

What is the power of a Turing-machine that cannot write? So it can still read and go back and forth on the tape, but it cannot write. I am wondering what this would be equivalent to in the ...
0
votes
1answer
30 views

Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$

I am looking for an unrestricted grammar which generates the following language: $\{ a^1\#a^2\#a^3\# \dots \#a^k \mid k >0 \}$ That is, words like $a\#aa\#aaa\#aaaa\# \dots \# \text{$k$ times '$a$...
0
votes
0answers
15 views

Turing machine for $s^{2i+j} d^j c s^i$

What would be a deterministic single tape Turing machine for the language $L = \{s^{2i+j} d^j c^1 s^i \mid i,j \ge 0\}$ over the alphabet $\{s,c\}$? Can someone draw an example? I am trying to ...
1
vote
1answer
46 views

Trying to prove semidecidability of an undecidable language

I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, ...
0
votes
0answers
16 views

Understanding the computational power of neural networks

It is known that a recurrent neural network with rational weights is computationally equivalent to a Turing Machine (a proof can be found in this paper). I don't understand how is it possible, it ...
1
vote
1answer
27 views

Reduce ATM to the language of TM encodings where if the TM accepts w then the TM accepts ww

Today I did a test in my class, the trace was: Prove that the language $L =\{\langle M\rangle\mid \forall w \in \{0,1\}^\ast: M \text{ accepts }w\implies M \text { accepts }ww \}$, is undecidable ...
0
votes
1answer
48 views

Can a Turing Machine tell if an input string is a description of itself?

Can some Turing Machine $M$ with description $\langle M\rangle$, check if an input string $w$ is a description of itself? That is, can $M$ be constructed such that $M$ can tell if $w$ = $\langle M\...
1
vote
0answers
37 views

Power of Turing machines that are not allowed to overwrite the input string [duplicate]

The question asks what kind of languages (regular, context free) can a Turing machine accept if you are not allowed to overwrite the input string. The initial configuration of the machine is start ...
0
votes
0answers
10 views

Proving that a language is undecidable [duplicate]

I'm trying to show that the language $L$ = {$<M,w>$ | $M$ is a TM that accepts $\overline{w}$} is undecidable, where $\overline{w}$ is the bitwise complement of $w\in \{ 0,1\}^*$. I know that ...
0
votes
0answers
22 views

Why do we need an opposite machine to prove that Acceptance problem is undecideable?

It is not clear why almost every book uses an opposite Turing machine to get a contradiction. Here in slides they also use the Machine Dwhich simply outputs ...
0
votes
0answers
127 views

Reduction from membership problem

i'm preparing for my exam from Formal languages and automata and i've found one example, which i don't know, how to deal with it. I've a language A with some rules and i need to prove using reduction ...
-1
votes
2answers
75 views

Is a Turing machine too strong of a model to model physical computation?

I've heard many times people debate the possibility of a real world computation that is impossible for a Turing machine, especially in the context of a human mind. Implying that the Church-Turing ...
0
votes
0answers
33 views

How to prove that a generalised queue automaton is equivalent to a Turing Machine?

I understand that a language can be recognised by a queue automaton (QA) if and only if it can be recognised by a Turing Machine (TM). This theorem states that it is possible to simulate a TM using a ...
0
votes
1answer
18 views

Regarding time complexity of multi-tape Turing machines

So let's say I've implemented an algorithm running in $O(n^2)$ on my 3-tape TM. What kind of time complexity would I expect for a single-tape TM? I just don't know where to get started...
1
vote
1answer
20 views

How to think when devising a TM that decides if a DFA rejects some string?

The title should explain my question thoroughly enough. I can't seem to get started anywhere. Intuitively it seems like some kind of brute-forcing would work i.e if the DFA has the symbols $\Sigma$ ...
0
votes
0answers
62 views

Language of intersection of Turing Machines

Consider the language below, I am trying to determine whether it is decidable or not. {⟨M,N⟩ | All strings in L(M)∩L(N) begin with 110.} I think that this language is not decidable. Using Rice's ...
0
votes
0answers
42 views

Decidability of the language of a TM whose head never moves left on input

I have had a question, which has already been asked in this community and marked as Duplicate, but the answer did not make sense to me, so I wanted to post for myself, hoping I will get some ...
1
vote
2answers
19 views

Turing machine to output enumeration of a language

I am trying to write a Turing machine enumerator that enumerates the language where $w = 0^n1^n$ and $n ≥ 0$. So for example it should output the following to the first tape: ...
0
votes
0answers
25 views

Is this language of TM pairs, defined via properties of their languages, decidable? [duplicate]

Lets assume we have the following language $$\{\langle M, N \rangle\ | \text{ All strings in } L(M) \cap L(N) \text{ begin with 110.}\}$$ How would we go about proving its decidability? Thanks.
0
votes
0answers
20 views

Turing machine for a variant of $a^nb^mc^{n+m}$

I'm trying to build a Turing machine to recognize the following entries: ...
0
votes
0answers
48 views

Is it decidable that a given Turing machine never moves left on a given input? [duplicate]

$$\{\langle M, w\rangle\mid M\text{'s head never moves left on input }w.\}$$ My second thoughts for this problem is that is should be decidable. We can make a Turing Machine that takes as input and ...
2
votes
1answer
41 views

Decidability of Turing Machine accepting exactly 14 words

Would you say that the following problem is undecidable? $$L_1 = \{\langle T \rangle \mid T \text { accepts 14 words}\}$$ My intuition says that this must be undecidable, and I want to try to reduce ...
0
votes
1answer
46 views

Is the language of all TMs accepting all strings starting with 010 decidable?

I am trying to figure out if this language is decidable: $$ \{ \langle M \rangle \mid \text{$M$ accepts all strings starting with 010}\}. $$ My intuition is that it is. Whatever string $w$ starts ...
0
votes
1answer
25 views

A,B decidable: proof that A\B is decidable too

For an assignment I have to proof that for two given decidable languages A,B, A\B is decidable too. My idea is as follows: If B is empty or doesnt have elements in common with A, then A\B is ...
1
vote
1answer
46 views

Prove $L = \{M \mid L(M)\text{ is infinite}\}$ is not Turing-recognizable

I'm supposed to prove this through mapping reducibility. I think I'm supposed to show that $A_{\mathrm{TM}} \le_\mathrm{m}\overline{L}$, which means that $\overline{A_{\mathrm{TM}}}\le_\mathrm{m} L$ ...
1
vote
2answers
56 views

Can I program a universal Turing machine to accept arbitrary input encodings?

I've been reading about building Turing machines for specific purposes, and some sources talk about input encodings and some talk about programming specific machines, but I've been unable to find ...
0
votes
1answer
14 views

Proving a set is semi-decidable

Let $S = \{ ⟨M,q⟩ | (\exists x) M $ reaches state $q$ when running $M$ on $x$$\}$, where ⟨M,q⟩ is coded TM M and state q. To prove that $S$ is semi-decidable, I've tried to use the equivalence: ...
3
votes
2answers
68 views

Does Halts reduce to all other undecidable languages?

In a CS theory class I'm taking, we showed Halts was undecidable via a diagonalization argument. All other undecidable problems we looked at we either got by reducing Halts to them, or some chain of ...
0
votes
1answer
42 views

Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages?

$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$...
0
votes
0answers
22 views

All the ways in which Turing machines are used

The Turing machine model can be used to do computation in several ways. Two ways I know are: For a Turing Machine that checks whether a particular string is present in a language or not, when the ...
1
vote
1answer
16 views

Circuits vs Turing Machines in the “nonuniform model of computation”

I just started learning about circuits in Chapter 6 of "Computational Complexity". There is an emphasis on the fact this model of computation allows different circuits for different input sizes of the ...