Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
2,043
questions
0
votes
1answer
10 views
Turing machine without return equivalent to Finite Automaton, PushDown Automaton or Turing Machine?
I have seen that a Turing machine without return is a Turing machine $M$ which at each stage of its calculation systematically moves its read / write head to the right.The aim of the exercise is to ...
0
votes
0answers
15 views
Design a Turing Machine for binary addition
I have been working on the following problem:
{0,1}∗ → N that treats a word of {0,1}∗ as the binary representation of a non-negative integer, with the last symbol being the least-significant. So bin(...
0
votes
1answer
23 views
Diagram to represents words having as many $0$ as $1$
Give the diagram of transitions of a Turing machine to a ribbon which
accepts the language on the alphabet $\{0, 1\}$ of the words which contain
as many $0$ as of $1$. (Note well that the $0$ and the $...
0
votes
1answer
31 views
How to prove (un)decidability
Let's say we have a string s , a code size limit of b bytes and a time limit t, the question is then whether or not it is possible to construct an algorithm that prints the string within the time ...
-3
votes
0answers
17 views
prove that every Turing recognizable language L is Turing-reducible to HALT
a language L is decidable if there exists a Turing machine M such that M(x) accepts for all x ∈ L and M(x) rejects for all x ∈/ L. Also, M is Turing recognizable if there exists a Turing machine M ...
-2
votes
0answers
7 views
Is the following language decidable and/or recursively enumerable? Input: A Turing Machine M. Question: Is |L(M)| ≤ 1?
Want to know whether the following language is decidable and/or recursively enumerable:
Input: A Turing Machine M.
Question: Is |L(M)| ≤ 1?
-3
votes
0answers
23 views
language L=<E,n> E is an enumerator, n is a number
language L=<E,n> E is an enumerator, n is a natural number. <E,n> means strings enumerated by E with length n. Is L recognizable? Is L decidable?
2
votes
0answers
13 views
Is there any known method to simulate a UTM with an instance family of the three body problem in physics?
I think it would be challenging since the three body problem is about continuous movement and Turing machines execute in discrete steps.
1
vote
1answer
397 views
Decidable? If a Turing Machine M, on input w, will M ever move its read/write head to the left?
If a Turing Machine M, on input w, will M ever move its read/write head to the left?
Determine if this violates Rice's Theorem.
1.
I think the answer for Q1 is decidable because we can make a Turing ...
0
votes
1answer
33 views
What is this turing machine doing
There is a following Turing machine. I want to understand what it is doing :
I tried running it on input 100, 10000. Both these strings are accepted whereas 10,1000 are rejected
That leads to a ...
-1
votes
1answer
16 views
Show that a language is not decidable by reducing from ATM
Let (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$)
show that the language L={<M1,M2,w> | M1 and M2 both accept or reject w} is undecidable by reducing
ATM ...
0
votes
1answer
17 views
Decidability of directed strongly connected graphs
Consider the problem of determining if a directed graph is strongly connected.
How to phrase it as a language and prove that it's decidable.
My Thoughts :
To think of decidability given a graph I ...
0
votes
2answers
31 views
0
votes
0answers
41 views
What are the technical reasons for which the empty string is not allowed to be accepted by a Turing machine?
Below are the excerpts from the automata text by Peter Linz.
Definition 9.3
Let $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ be a Turing machine. Then the language accepted by $M$ is
$$L(M) = \{ w \...
0
votes
1answer
56 views
TM decidability using pigeonhole principle
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,...
0
votes
1answer
14 views
Show that a set is turing reducible to another set
Consider an operator $+$ defined on $P(N)$ as follows: $A + B = \{2x\mid x \in A\}\cup \{2x + 1\mid x \in B\}$
Show that both $A$ and $B$ are Turing-reducible to $A+B$
I am kind of confused about this ...
0
votes
1answer
23 views
TM with double-infinity tape semi-decides the same languages as classical TM
Show that a Turingmachine with tapes that are infinite in both directions semi-decides the same languages as a classical TM. Apart from the entry-word, the tapes are filled with empty spaces and the ...
0
votes
1answer
34 views
Show that LOOP is reducible to Complement of Halting problem
LOOP = {<M,w1,w2,w3>: M is a Turing machine that doesn't halt on at least 2 of the wi}
HPC = {<M,w> : M is a Turing machine that doesn't halt on w}
Show that LOOP is polynomial time ...
0
votes
1answer
26 views
Show that this language is decidable?
Let A = { | M is a DFA which doesn't accept any string containing an odd number of 1s}. Show that A is decidable.
The questions seems simple so I designed the following TM D that decides whether ...
1
vote
1answer
12 views
What is a self-delimiting program?
I came across the term self-delimiting program, referring to the paper "Laws of information (nongrowth) and aspects of the foundation of probability theory" by Levin, 1974.
Unfortunately ...
1
vote
1answer
44 views
Prove/Disprove: NP is closed under “mixed” complexity
Let $\displaystyle S_{1} ,S_{2} \subseteq \{0,1\}^{*}$, we say $\displaystyle x\in S_{1}°S_{2}$ if it's of the form $\displaystyle x=x_{1} x_{2} ...x_{n}$, for $\displaystyle n$ even, such that:
$\...
1
vote
0answers
34 views
Determining whether a language $L_{a}$ is recursively enumerable
I'm trying to determine whether a language $L_{a}$ is recursively enumerable, but first I'm having trouble deciphering the definition $L_{a}$ given the following question:
Given an recursively ...
0
votes
1answer
24 views
Converting a special case TM to a regular TM
So, I have been given a TM where the head can access and write both the character that the head is pointing at and the next character to the right.
So if we have a TM abbb and the head is pointing at ...
0
votes
2answers
28 views
Proving that Turing decidable languages are closed under reversal
I need to prove that Turing decidable languages are closed under reversal. I have no idea on how I would prove this. Any suggestions or clues?
3
votes
1answer
86 views
Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem?
Say I'm given an oracle that tells me whether or not $L(M)$, the set of words accepted by a Turing Machine $M$, is finite.
By leveraging this oracle, can I solve the halting problem? That is, on an ...
1
vote
1answer
46 views
Regarding a theorem that says a language that is Turing-Recognizable iff some enumerator enumerates it
I am reading the proof of Theorem 3.21 in Sipser's textbook.
Theorem 3.21 A language is a Turing Recognizable iff some enumerator enumerates it.
First direction (<==).
Given an Enumerator E that ...
2
votes
0answers
57 views
Decidability of Narcissistic Language Using Turing Machines
I've been working on decidability practice problems and I came across this one in a practice problem set from the textbook An Introduction to Computational Techniques. I know the steps for how to ...
0
votes
1answer
32 views
Undecidability and Unrecognizability of Language with two Turing Machines
I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the ...
-3
votes
2answers
62 views
Prove that the language Cats-Vs-Dogs is undecidable
Define Σ = {a, b, c, . . . , z} be the set of letters in the English alphabet.
Prove that the following language is undecidable:
Cats-VS-Dogs = {(M) | Either “cats” ∈ L(M) or “dogs” ∈ L(M), but not ...
-2
votes
1answer
35 views
How to prove the language L that contains all Turing machines M where L(M) is recognizable is decidable?
How to prove that $L$, where
$$L = \{\langle M\rangle: L(M)\text{ is recognizable}\}$$
is decidable? What about $\bar{L}$?
1
vote
1answer
50 views
Polynomial time verification of Graph Isomorphism problem
Using guess and check method, for two given graphs with the same number of nodes, a NTM selects a permutation of the node set and then checks if the edges are preserved.
The nondeterministic selection ...
1
vote
1answer
24 views
Turing machine - definition of program - naive question
In the paradigm of Turing machines what is considered a program?
Can't find a definition anywhere.
Is it a member of L(M)?
0
votes
2answers
43 views
Can the intersection two non-recursive sets be recursive? Prove it
I am still really new to compsci theory and some of the topics are really hard to understand. For this Problem I would think that say we have two sets A and B and they are both non-recursive.
If we ...
0
votes
2answers
26 views
How can a machine with fixed output for all inputs be considered a Turing machine?
From this answer, and the comments that follow:
To clarify, this machine T′ with the fixed output for all inputs is a Turing machine? – Shashank V M
@ShashankVM, Yes, T′ is a Turing machine. – D.W.♦ ...
0
votes
1answer
38 views
When can a deterministic finite-state-automaton (DFSA) along with its input sequence be said to be a part of another DFSA?
For a Finite State Automaton / Finite State Machine (FSM) $F$, that has an input alphabet, a set of possible states, an initial state, a set of possible final states and a state transition function, ...
-3
votes
1answer
29 views
How to simulate two counters using one (FIFO) queue?
How to simulate two counters using one (FIFO) queue? (In terms of algorithms, unary stack.)
0
votes
0answers
56 views
How to implement a Turing Machine that calculates log base 2 of n where n is a natural number and output in a unary format? [duplicate]
How would you construct a Turing Machine that calculates log2(n)?
The process must take in an input such as 4 and output the result in a unary format such as a 11 (11 = 2 in unary)?
In the final ...
1
vote
1answer
316 views
Turing machine to compute $⌈\log_2n⌉$ with 1 tape and unary input/output
I'm trying to figure out how to make the action table for a Turing Machine computing $⌈\log_{2}(n)⌉$. The input and output shall be unary (meaning $3$ should represent $111$). I can only deal with 1 ...
-1
votes
1answer
65 views
For every Non Deterministic polynomial Turing Machine $M$ exists $L(\overline{M})\in P \Leftrightarrow P=NP$
The $\Leftarrow$ direction is straightforward.
On the other hand for $\Rightarrow$ direction I have an idea of the prove but I don't sure about it.
For NTM, Non Deterministic Turing Machine, $M$, for ...
0
votes
1answer
26 views
Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$
When $\overline{M}$ is a non-deterministic polynomial by time Turing machine that final states switched: accept to reject and vice versa.
I'm thinking that this equal to $P=NP$, but I saw a solution (...
0
votes
0answers
30 views
Deterministic CSL = semi Deterministic CSL
How can it be proven that a
deterministic CSL = semi-deterministic CSL?
Does that imply that a CSL = semi CSL?
Would I need to build a Turing machine, since a language accepted by a Turing machine is ...
0
votes
0answers
49 views
Proof that CSL ⊊ REC
I'm trying to prove that a context sensitive language ⊊ Turing-acceptable language.
I was thinking of working out the complement of the language $A$, where $A$ consists of all words $w$ such that $M_w$...
1
vote
1answer
21 views
Can a Turing machine or Push Down Automaton construct languages of type 3?
I am not quite sure, whether automata can construct languages over their types. For example, a Push down automaton can construct a language of type 2 - does that mean that a PDA also can construct a ...
1
vote
0answers
20 views
Time constructible function T in equivalence of Turing Machines
I'm reading Computational Complexity by Arora and Barak and I had a doubt regarding a statement made about the equivalence of Turing machines:
For every $f\colon \{0, 1\}^∗ → \{0, 1\}$ and time-...
1
vote
2answers
41 views
Turing machine that checks whether a given string is an output of a given machine and input
Is there a Turing machine such that, given a description $\langle M \rangle$ of a Turing machine $M$, an input $x$ and a string $y$, computes whether or not $y$ is the output of $M$ input $x$?
My ...
2
votes
2answers
81 views
Why can't we compute the lexicographically-least word of a given length on which a given TM halts?
I had this question in my exam. but my answer is wrong(I didn't receive explanations why...)
$$f(\langle M\rangle,1^n)=\left \{ \texttt{the lexicographically smallest } x\in\left \{ 0,1 \right \}^n \...
0
votes
1answer
35 views
Deteremine if Language is in $R$ or $RE$
$$L =\left \{ \langle M \rangle \mid \exists x\in \Sigma^* \left(\left | x \right |\leq 10000 \wedge H(M, x\right) \right \}$$
Where $H(M, x)$ denotes whether Turing machine $M$ halts on input $x$.
My ...
1
vote
1answer
21 views
Turing machine that decides $A=\{0^{2^n} | n \ge 0 \}$ with an alphabet of two symbols
I need to build a turing machine that decides $A=\{0^{2^n} | n \ge 0 \}$ with an alphabet of two symbols - $\{0, \_ \}$.
I'm aware of the known TM that decides this language with three symbols $\{0, x,...
-1
votes
1answer
19 views
How to construct the following turing machine?
Construct a turing machine (TM) over the alphabet {a,b,0,1,#} that reads strings of the form (ab)^n with n>0. If the string w on the tape has this structure, the TM should overwrite all letters ...
1
vote
1answer
91 views
Must a Turing machine tape be binary?
I once asked why does computer data bits are usually organized on binary (base 2) sets, rather than on unary (base 1) sets, aiming to also understand why its not also ternary (base 3), heptary (base 7)...
