Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
2,198
questions
0
votes
0answers
2 views
Undecidability of a set of Turing Machines
Considering the following set, I have to say if it is undecidable, decidable or semidecidable:
$$S_1 = \{y | \forall n \text{ the Turing Machine } M_y \text{ does not accept any string of length } n\}$...
0
votes
0answers
7 views
Design a two-tape deterministic Turing machine M that recognizes the language L3= {x#(0^k) #y : x, y ∈ {0, 1}* , x = y ∧ |x| = k}
I'm having a hard time trying to write a two tape Turing machine
I wanted to first think Oh all I'd have to do is scan from left-to-right till I find the strings that matches the accepted strings) ...
3
votes
1answer
43 views
How is the time complexity of a non-deterministic Turing machine defined?
I read different things online about this:
In Sipser, p. 283. The time-complexity of a NTM is defined as the maximum number of steps it uses on any branch on any input of length n.
So this is only ...
0
votes
1answer
19 views
What does c represent in Sipser's explanation of the modified post correspondence problem Introduction to the Theory of Computation book?
I'm supposed to perform actions corresponding to the different steps in Sipser's explanation of the Modified Post Correspondence Problem, but I'm not sure I understand the third step.
The part I'm ...
-2
votes
0answers
39 views
Prove that {⟨M,u⟩ : M is a DFA and there exists w ∈ L(M) such that u is a subword of w} is decidable
Let $u,w\in\Sigma^*$. We say $u$ is a subword of $w$ if there exist words $x,y\in\Sigma^*$ such that $w = xuy$. Define the language $$\mathrm{SUB}_{\mathrm{DFA}} = \{\langle M,u\rangle : M\text{ is a ...
1
vote
1answer
31 views
Showing Turing machines are more computationally powerful than Finite State Machines
I've been pondering on whether Finite State Machines, particularly Mealy machines, can describe any computable function as Turing machines do. However "Mealy-computability" does not seem to ...
0
votes
0answers
20 views
Turing Machine that accepts L(M1) = {x^n y^2n z^n | n ∈ N}
I'm trying to design a Turing machine that accepts all strings in the language $$\{x^{n}y^{2n}z^{n}|\ n\in N\}$$ but I'm having trouble getting it to accepts when n> 1, for some reason it rejects ...
1
vote
0answers
15 views
Proving set of register machines that halt before k steps for some input is non-recursive
Given an enumeration of register machines $R_n$ that take a single natural number as input, and a constant $k$, the function $f$ is defined as:
$$
f(n) = \begin{cases} 1 & \exists m \text{ such ...
0
votes
3answers
201 views
How it's possible decide CNF by having a turing machine that decide SAT?
Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
0
votes
0answers
19 views
Is there any problems with equating Turing Machines with Algorithms and Language with Problems?
In a lot of the online explanation of complexity theory, the author proposes the following.
"The definition associated with complexity theory (e.g., definition of
NP) is phrased in terms of ...
0
votes
1answer
22 views
Turing machine accepting square
I'm trying to figure out following assignment and I could use your help, because I'm stuck.
Task:
Construct a Turing machine accepting words in format $1^k$, where $k=n^2$, $n$ being an integer. ...
1
vote
1answer
43 views
Is the language containing Turing machine $(M_1, M_2)$ such that $L(M_1) \cup L(M_2) = \Sigma^*$ decidable?
We are given two Turing machines $M_1$ and $M_2$ and we wish to decide whether the union of the language $L(M_1)$ accepted by $M_1$ with the language $L(M_2)$ accepted by $M_2$ coincides with $\Sigma^...
-2
votes
0answers
19 views
Can I minimize this turing machine like this?
This is the original turing machine as taught by our professor. For even palindrome to be specific. B is the blank symbol here.
This is the turing machine that I made.
-2
votes
0answers
32 views
Turing machine for addition
I want to make turing machine for addition.
So say I want to add 2+3.
I say 110111.
What I want to do is convert 0 to Blank and bring it to the leftmost part. Then the resulting answer is final ...
-2
votes
3answers
99 views
What is the point of encoding universal turing machines?
I am unable to understand why do we need to encode turing machine at all? I heard that we are trying to build a programmeable turing machine but can't relate how encoding it will make this ...
1
vote
1answer
25 views
A turing machine L takes a machine <M> which has to halt at for least n Inputs
I've been wondering about this problem for a while:
Say we have L = { <M>, n | M has to halt for at least n Inputs}
and multitapes are simulating various inputs bla bla
How do I count how many ...
-2
votes
1answer
52 views
Halting problem is undecidable proof-:
Confused with this proof. I will point my confusions here.
what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine? How do we decide w is ...
0
votes
0answers
20 views
A query regarding equivalence of Parallel vs. Serial cells Turning Machine
Given: A Turing machine (set of programs) that behaves as follows:
It has some fixed number of states $(S)$ and binary alphabet $(0/1)$.
For some constants $k, p, (k<N, p< N)$:
Its read/write ...
0
votes
1answer
44 views
What happens to a Turing Machine if it enters final state but the input is not yet read completely?
In the image, the language of the TM is defined on (a, b, c, d) and there is no transition on final state, but strings consisting of d are also part of the language.
In all TM problems I have seen ...
2
votes
0answers
109 views
Proving that a specific Turing machine accepts a regular language
Calling all math buffs! ;)
A Turing machine has two states - one accepting and one non-accepting. Furthermore, the Turing machine cannot overwrite blank symbols. (Note: It's assumed that the blank ...
-1
votes
0answers
16 views
Group input string by 4 characters by adding " " with a Turing Machine
I have this problem, where I have an input where:
alphabet of the input string is Σ = {a,b,c}
need to add a " " after every 4 characters.
Example: Input = "aabacc", Output = &...
1
vote
0answers
39 views
Simple example of LogSpace reduction
In general, how can I verify that my many-one reduction is a LogSpace reduction? E.g. I was looking at the proof of HORN-SAT is P-complete via logspace reduction.
It would be ok even if someone makes ...
0
votes
2answers
69 views
How does a CPU do function calls?
Besides basic instructions for a general-purpose computer (binary arithmetic, move instruction, and jump on condition), it seems you can't implement a universal turing machine (is that even the right ...
2
votes
2answers
167 views
Why can't I use a polynomial-time reduction for proving P-completeness?
According to the Wikipedia page on P-complete,
a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate ...
0
votes
1answer
27 views
What is the runtime overhead and how many more states are needed for simulating a TM whose head may remain stationary by a standard TM?
The standard Turing Machine (TM) can only move left and right.
When I simulate a TM whose head may remain stationary and I execute the stationary move, then I need to make two steps with the standard ...
0
votes
2answers
46 views
Can a non-recognisable language have a recognisable subset?
If $L\notin$ RE, can there be a language $L'\subseteq L$ such that $L'\in$ RE? Or is it necessarily true that $L'\notin$ RE for all $L'\subseteq L$.
-1
votes
0answers
16 views
Let L be the set of Turing machines M with input alphabet Σ such that M writes the symbol a ∈ Σ at some point on its tape. Show that L is undecidable [duplicate]
Can some help me how to write the answer for this. I am not able to make way how to prove that it is undecidable.
1
vote
0answers
29 views
Lack of "Any" scan for Turing Machines
I was reading Charles Petzold's The Annotated Turing that walks through Turing's original proof out of curiosity and feel like I've missed something during the part where Turing is describing ...
1
vote
1answer
53 views
If a TM accepts a non-regular language, its space complexity is $\Omega(\log \log n)$
I have been given an assignment that I'm having a very hard time understanding.
The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is $\Omega(\log \log n)$ (...
0
votes
1answer
25 views
no-input Turing Machine which accepts in k or fewer steps
Can we prove by induction that $A_k$ is computable for every choice of $k \in \mathbb{N}$?
$A_k$ is the set of descriptions of a no-input Turing Machine which accepts in $k$ or fewer steps.
1
vote
0answers
26 views
Which is the best theory of computation/automata/formal language book for practice problems(unsolved)? [closed]
I have
Introduction to automata theory, languages and computation by hopcroft, rajeev motwani, jeffrey d ullman
Elements of the theory of computation HR lewis Christos H papadimitriou
Theory of ...
1
vote
1answer
22 views
The recognizability of $\overline{A}_{TM}$
In undergrad theory classes, the idea of decidability and recognizability is introduced. It's well known that $A_{TM}$, the set of words accepted by a TM $M$, is recognizable but not decidable. We ...
2
votes
1answer
69 views
Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps?
Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps?
I've read the similar questions and answers such as here, but I wanted to ...
0
votes
2answers
99 views
Does allowing a mutable transition function in Turing machine make it more powerful?
as the title says does having a mutable transition function make the Turing machine more powerful
by mutable I mean we have a set of transition functions that we can choose one of them arbitrary based ...
0
votes
1answer
77 views
Language and Decidability Problems for Turing Machines
Below are the two problems Im working on and my attempt at a solution (understanding the question). My first question is am I interpreting the question from the symbols right, second can you help ...
0
votes
0answers
28 views
Is it possible to build a linear bound automata that decides A(NFA)?
Is it possible to build a linear bound automata that decides A(NFA)?
A(NFA)=Accepting Non deterministic Automata - language that contains the encoding of all the NFAs together with the strings that ...
0
votes
0answers
108 views
Turing Machine for Check Validity of Unary Multiplication (A=B*C)
I have a lot of difficulty with the turing machines. I understand the theory well, but I need help with a lab exercise...
Design a SINGLE TAPE Turing Machine that accepts the language $a =
> b \...
0
votes
1answer
38 views
What is wrong with this "proof" of $coNP = NP$? [duplicate]
I am wondering why the following "proof" of $coNP = NP$ does not work:
$\subseteq:$Let $L$ be a language in $coNP$, that means there is a non-deterministic Turing Machine $M$ that decides ...
0
votes
1answer
28 views
Is it true that $P = coNP$?
I have recently read the definition of $coNP := \{L \ \mid \ \overline{L} \in P\}$, where $L$ denotes a language. However, I am wondering what the difference between $P$ and $coNP$ is, since an ...
0
votes
1answer
45 views
Reduction of RE and Rec languages
Suppose $L_1$ is reduces to $L_2$ in polynomial time, $L_1\leq_p^\mathsf{}L_2.$ we know that if $L_2$ is RE then $L_1$ is also RE and $L_2$ is REC then $L_1$ is also REC.
And also I know that if $...
-1
votes
1answer
40 views
Does Turing machine move left on particular input?
We know that RE language is the collection of unrestricted grammar which is known as type-0 grammar that's why emptiness, finiteness of every RE languages is undecidable. My question is how I check ...
0
votes
0answers
31 views
Why linear bounded automata emptiness and finiteness isn't decidable? [duplicate]
We know that linear bounded automata has tape size based on input size which is limited. Context-sensitive languages are accepted by LBA. My question is that if LBA has limited tape size why it's ...
2
votes
2answers
97 views
Mathematical models of computation that capture more advanced OS and CPU design features
The universal Turing machine is the standard theoretical model of a stored-program computer. While in one sense as general as possible (Turing completeness), it doesn't explicitly contain many of the ...
1
vote
1answer
59 views
Is Brainfuck, but you can only move the tape into one direction or rewind it to the beginning, Turing complete?
If you take Brainfuck and modify '<' to move the tape head to the beginning of the tape, would this modified Brainfuck still be Turing complete?
It feels like it should be, but I can't wrap my head ...
0
votes
1answer
151 views
Why REC languages is undecidable under emptiness and finiteness?
Membership problem of Recursive languages are decidable.
My approach:
Let $L$ be a recursive language and $M$ be the Turing Machine that accepts it.
For string $w,$ if $w ∈ L,$ then $M$ halts in ...
0
votes
2answers
37 views
Can you help me provide some examples of 3-co-SAT?
Recently I'm studying 3SAT problem, which is a NP-complete problem. I feel that it's easy to find a boolean formula which is satisfiable,but how about boolean formulas which are unsatisfiable， namely ...
1
vote
1answer
44 views
Could I apply Rice theorem for both TM's property and language property?
I read that Rice theorem applicable only for language property not for machine property. But today I have read from stack exchange and one site they are applying Rice theorem on machine also. My ...
0
votes
1answer
51 views
What are the differences/relationship between 2D Turing Machines and Cellular Automata
I have been reading up on 2D Turing machines on wolframscience and I am kind of confused about what exactly is the relationship between 2D Turing machines (like Paterson's worm and Langton's Ant) and ...
0
votes
0answers
50 views
Efficient Turing machine to check that an unary multiplication is valid
I'm trying to find an efficient one-tape Turing machine that accepts inputs in the form R=A*B iff the equation is indeed true. All three numbers are written in ...
1
vote
1answer
17 views
The Turing Machine in the proof of Time Hierarchy Theorem
In the proof of the Time Hierarchy Theorem, Arora and Barak writes:
Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate ...
