Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
1,995
questions
1
vote
0answers
15 views
Correct terminology for $P1;P2$?
This question is about the correct terminology. Let $P1$ and $P2$ be two LOOP programs. Then $P1;P2$ is also a LOOP program, which executes $P1$ and then executes $P2$. Would this be called ...
0
votes
0answers
22 views
Is my assumption about non trivial propery correct?
"make sure you understand why for a non trivial property $S$, $\bar{S}$ is also non trivial"
My assumption is: $S$ is non trivial property: There are L1,L2 such that $L_{1},L_{2}\in RE$ and ...
-5
votes
0answers
22 views
Does this Turing machine accept the following input: abcab
I'm trying to solve this Turing machine but so far I haven't managed it. Does it accept the following input: abcab ?
0
votes
1answer
19 views
Single tape Turing Machine that accepts string with at least five G's and at most three T's?
I am looking to create a single tape acceptor Turing machine acting upon the language of any ASCII string, that would only accept strings that contains at least five G's and at most three T's, and ...
0
votes
1answer
39 views
Is a language recursive? 2 wrong ways of solving
Let's define:
$Disagree(M_1,M_2) = \{x| $The result of $M_1$ on $x$ different from the result of $M_2$ on $x\}$
that means: if $M_1$ accept, $M_2$ reject and vice versa
$NPA=\{L|\exists M_1,M_2$ ...
0
votes
1answer
29 views
Using Rice's theorem to prove undecidability of $E_{TM}$
I saw this proof and I wondered if I could prove $E_{TM}$ with Rice's theorem similar to the one described in the answer. Can you do the same thing by letting $M$ to only accept empty strings? (the $M$...
0
votes
1answer
32 views
Reduction from $A$ to $B$ as execution of Turing machines
As explained in answers to this question, reduction from $A \le B$ can be represented in the following way.
But in this example:
from here
At least as I understand it:
The reduction is from $\...
1
vote
2answers
48 views
Reduction as a flowchart
I'm trying to understand the reduction as a flowchart graph.
Let's say the boxes $A$ and $B$ are TMs/Functions and $x$ is the input.
Is this plot represent reduction from $A$ to $B$ ($A\le B$) or ...
-3
votes
1answer
26 views
Decidability of whether $w \in L(M_1) \setminus L(M_2)$
I'm studying for my finals and I came across this question from past exams:
Is the following language decidable?
$$ L = \{ \langle M_1,M_2,w \rangle \mid w \in L(M_1) \setminus L(M_2) \}. $$
How can ...
2
votes
1answer
41 views
Is this a correct application of Rice-Shapiro theorem?
Let $\langle M\rangle$ be the encoding of a Turing machine as a string over $\Sigma=\{0,1\}$, and consider the language $L=\{\langle M\rangle| \text{ $M$ is a Turing machine that accepts a string of ...
2
votes
2answers
80 views
Proving decidability
Regarding the following languages $L_1$ and $L_2$, I want to prove that $L_1$ is decidable and $L_2$ is undecidable. I want to construct a turing machine which can decide $L_1$ and reduce the halting ...
4
votes
1answer
65 views
Proof that $P\subseteq NP$ without nondeterministic TM
I know the proof that using nondeterministic TM, but as I understood there is another proof without nondeterministic TM.
If you answer please write with as much details as you can.
1
vote
0answers
82 views
How can I simulate nested WHILE loops in a theoretical programming language to show Turing completeness?
PRE-WORK-POST is a theoretical programming language with the following structure, where P,Q and R are LOOP program:
$$\text{PRE} \ P \ \text{WORK} \ Q \ \text{POST} \ R \ \text{END}$$
First $P$ is ...
1
vote
1answer
12 views
Unrecognizability of functional variant of halting problem
Let $L_0 = \{ \langle M, w, 0 \rangle \mid M \text{ halts on } w\}$ and $L_1 = \{\langle M, w, 1\rangle \mid M \text{ does not halt on } w\}$.
In $\langle M,w,i \rangle$, the $i$ indicates a specific ...
4
votes
1answer
47 views
Explain the difference between Turing Complete and Turing Equivalence
I'm not sure if I understand the difference between Turing Complete and Turing Equivalent programming languages.
A computational system that can compute every Turing-computable
function is called ...
2
votes
1answer
53 views
Where to put the state in a two-stack push down automaton?
theoretically, the state is between the two kleene-stars of the work-alphabet
gamma* q gamma*
where q is the current state and each ...
2
votes
0answers
31 views
Understanding the simulate of an IF loop program through a LOOP program
We have the following operation $\text{IF} \ x_i =0 \ \text{THEN} \ P \ \text{END}$. I want to simulate this using a $\text{LOOP}$ program. Here is what I have:
$$\text{IF} \ x_i = 0 \ \text{THEN} \ P ...
0
votes
1answer
29 views
If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?
Suppose there is a polynomial time reduction from problem $A$ to $B$.
Why is the following false?
If $B$ is NP-hard then $A$ is NP-hard.
Can some explain this intuitively?
0
votes
1answer
144 views
Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable?
I thought to reduce from the halting problem to conclude undecidability, yet I don't know how to do it. Perhaps the problem reduces to other decidable problem, and thus it is also decidable?
2
votes
1answer
35 views
surprizing reducibility and challenge on it
Assume that Problem $A$ is polynomial-time reducible to problem $B$.
Claim 1: If problem $A$ is NP-hard then problem $B$ is NP-hard.
Claim 2: If problem $B$ is NP-hard then problem $A$ is NP-hard.
...
2
votes
2answers
145 views
Showing that the language L={āØM,wā© | M moves its head in every step while computing w} is decidable or undecidable
How would you go about showing that the language L={āØM,wā© | M moves its head in every step while computing w} is decidable or undecidable?
Intuitively speaking I think it is indeed undecidable because ...
2
votes
2answers
32 views
If $A \in \mathrm{RE}$ and $A \leq_m \overline{A}$ then $A\in \mathrm{R}$
I found the following question with an answer here, but I can't understand the steps of the solution.
Show that if a language $A$ is in RE and $A \leq_m \overline{A}$, then $A$ is recursive.
Solution....
2
votes
1answer
30 views
Halting (on empty input tape) for an infinite subset of all Turing machines
As is well known, there is no single procedure for deciding whether any given Turing machine halts on an empty input tape. This is easily shown, e. g., by applying Rice's theorem.
But what if, instead ...
0
votes
2answers
63 views
Decidability of Turing machines and misconceptions on the halting problem
In an online discussion on Turing machines and decidability recently, I blatantly theorized that any problem about a specific single Turing machine must be decidable, the question of undecidability ...
0
votes
1answer
30 views
De morgan's law in formal language
I found in some exercise in computation the following step:
I can't understand why is it equal terms, based of what I know about De morgan's law:
OR should be replaced by AND
where $w=\varepsilon$ ...
0
votes
1answer
69 views
How this language belong to R?
Consider the following language $$L= \{ \langle M\rangle | \text{ $M$ is a TM, and $L(M)\in coRE$} \}$$
I don't understand why the language $L$ is in $R$, intuitively, I think this is not true. ...
2
votes
1answer
54 views
What is the actual scope of the Halting Problem impossibility result?
Consider the Halting problem : No TM H exists which given any TM and input, decides whether that TM will halt on that input. The usual proof (informally) is that if such an H existed, then a function ...
2
votes
0answers
299 views
Prove that PRE-WORK-POST is Turing Complete
This is a homework question and I am trying to fully understand what I have to do and how to go about it. Therefore, I don't want full answers to the question.
The programming language PRE-WORK-POST ...
6
votes
5answers
3k views
I'm trying to understand why every language has an infinite number of TMs that accept it
I found the following answer:
$L_{17} = \{ \langle M \rangle \mid \text{$M$ is a TM, and $M$ is the only TM that accepts $L(M)$} \}$.
R. This is the empty set, since every language has an infinite ...
16
votes
4answers
3k views
Can one build a “mechanical” universal Turing machine?
This question connects different disciplines so it's awkward to choose a SE site for it, but I'll go with this one because here (I hope) the shared culture will make information transfer easier.
So ...
0
votes
1answer
21 views
Where is the problem in this proof that deciders are no stronger than LBAs?
So I've been working on a problem for fun and I'm worried I've run into some sort of contradiction, so I'm trying to figure out where I went wrong. I've simplified the issue down to this:
Decider ...
0
votes
0answers
35 views
How does a Turing machine simulate itself
I have a problem regarding Recursion Theorem in Computation Theory.
So Turing machines can have themselves as input. So they can simulate themselves(this technique have been used in many proofs i saw)....
1
vote
0answers
17 views
Time-Sensitive Reductions for Undecidable Problems
I'm studying Comparability and Complexity, and through the course, a number of problems (namely, the halting problem for Turing Machines, etc.) have been proven undecidable through elementary proofs ...
-1
votes
1answer
39 views
How to show a language is Partially Decidable?
I am trying to solve some questions on partial decidability of languages and I am getting confused in how to construct proper arguments through the idea of Universal Turing Machine.
I am not posting ...
0
votes
1answer
64 views
How can I do a subtraction on unary numbers terminated in X on turing machine?
For example, if I have 11X1111X as input, the result should be X. For another example, input: 1111XX -> 1111X. I am a complete beginner and all my tries so far failed to meet the expectation.
This ...
0
votes
0answers
19 views
What's the union between a decision problem and its complement
I see the union of problems as something like this:
$P=F\cup G$
$P(\omega):$
$\;\;\;\;if\; F(\omega)==True: return \;\; True$
$\;\;\;\;else\;if\; G(\omega)==True: return \;\; True$
$\;\;\;\;else: ...
0
votes
0answers
33 views
Let $f$ be a computable and injective function. Is $f^{-1}$ computable and injective?
So I just started learning about computability, undecidability and Turing machines. And I wonder if:
Given a computable and injective function $f$, is $f^{-1}$ also computable and injective?
I don't ...
1
vote
1answer
166 views
Is L = { <M,w> | M is a TM and L(M)={w}} turing recognizable? And its complement?
My approach is to prove that the complement is turing recognizable and undecidable, so that we can prove L not recognizable. But what is the complement of such L?
0
votes
0answers
22 views
Composition on functions computable in logspace requires always inner recomputation?
We have a composition logspace computable functions where the outer machine is one-way and the inner is a logspace verifier with a read at once certificate tape and output string (instead of "yes&...
1
vote
0answers
40 views
Show that if $P=NP$ then there is an algorithm that finds a witness for the language $L = \{x | \exists_w M(x,w)=1 \}$
Let $M(x,w)$ be a polynomial Turing machine with $|w| = poly(|x|)$, and $L = \{x | \exists_w M(x,w)=1 \}$.
Assuming that $P=NP$ I want to show that there is a polynomial algorithm $N(x)$ that finds a ...
2
votes
3answers
77 views
Why do we create universal turing machines?
Why do we create Universal Turing Machine explicilty to simulate the run of a word (say, $w$) on a Turing Machine $M$, given the description on it? Can't we just run $w$ on $M$ itself? I don't see the ...
0
votes
0answers
27 views
language for Turing machine, {w#w | w ā {0,1}*}
Recently, I am studying a computation theory and got a question regarding turning machine.
let {w#w | w ā {0,1}*} be the language of a turning machine. it will accept, for example, 01#01.
however, if ...
0
votes
0answers
22 views
Turing machine that recognizes the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$
I'm pretty sure that the Turing machine state diagram I drew accepts all strings in the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$, but how do you verify this? Likewise, how do you verify that this ...
0
votes
1answer
39 views
Show that if $SAT \in P/klog(n)$ then $SAT \in P$
Show that if $SAT \in P/klog(n)$ then $SAT \in P$
Assuming that there is a a constant $k \in \mathbb{N}$ such that $SAT \in P/klog(n)$, I need to prove that $SAT \in P$.
Since $SAT \in P/klog(n)$, ...
0
votes
1answer
32 views
Is the language Turing machine-Input pairs for which the computation loops recognizable?
I'm wondering if the following language is $L \in \mathsf{R}$, $L \in \mathsf{RE} \setminus \mathsf{R}$, $\overline{L} \in \mathsf{RE} \setminus \mathsf{R}$:
$$L=\{<M,w> \,\mid M \mbox{ Loops on ...
1
vote
1answer
23 views
Showing semidecidability without using diagonalization
All the methods I know which shows a given language $L$ is $RE$ but note $REC$ deep down boils down to the cantor's diagonalization arguement in one way or the other, and most commonly it boils down ...
0
votes
1answer
35 views
What is the correct definition of coNP/poly?
Complexity Zoo defines coNP/poly as
Complement of NP/poly
Thanks to Emil, I understand it as
"the class of decision problems whose complement can be solved in polynomial time by a non-...
0
votes
2answers
34 views
Is it decidable when a TM M gets another as inputs and checks if it fullfiills certain property?
I was asking myself if it is not possible to decide the language where a TM M gets the Godel number of a TM M' as input and the checks if, let us say, the TM M' has a certain amount of transitions.
My ...
1
vote
0answers
25 views
Does PromiseBPTIME have a time hierarchy theorem?
This is a follow-up to this question. Even though BPTIME does not have a time hierarchy theorem, the reasons that prevent it from having one are essentially bypassed by PromiseBPTIME. Thus, does ...
0
votes
1answer
142 views
Determine if a language is Decidable or semi decidable
Consider the language $L = \{\langle M \rangle: \text{ $M$ accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$.
We need to determine, without ...
