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 ...
