Questions tagged [turing-machines]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
6 views

EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it?

So as I understand $EQ_{TM}$ (problem of deceiding whether two turing machines are equivalent) is not Turing Recognizable (by showing that $A_{TM}$ is reducible to its complement ${NEQ_{TM}}$). But we ...
1
vote
2answers
103 views

is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?

My understanding is that a language cannot be decided if the language is actually infinite (not generated by any machine). However, actual infinites make me squirm. Is there any reason to believe in ...
1
vote
1answer
20 views

1-Tape Non-deterministic Turing machine and non-palindromes

I have to design a Non-deterministic 1-Tape Turing machine that accepts only non-palindromes in O (n log n). But my best shot was only in O(n^2). How can I use the properties of NTM on a single tape ...
1
vote
1answer
30 views

Explain the simulation of an if else statement in LOOP

I'm learning about LOOP program and in my book I have the following command which is simulated by a LOOP program: $$\text{if} \ x_i = 0 \ \text{then} \ \text{P1} \ \text{else} \ \text{P2} \ \text{end}$...
0
votes
1answer
27 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 ...
2
votes
1answer
45 views

this language and acceptance by queue automaton

I don't know how to prove or show that: $ L_1 = \{xx|x \in \Sigma^\ast\} $ (that can be accepted by queue automaton) If it would be possible, show by deterministic queue automaton, if not, by non-...
0
votes
1answer
60 views

Copy operation in under 9 states?

There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following ...
1
vote
1answer
22 views

A language is decidable iff it is Turing-recognizable and co-Turing-recognizable (WHY?)

I am trying to understand the proof for this theorem (theorem 4.22 of the book 'An introduction to the theory of computation'): ...
1
vote
0answers
26 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
1answer
34 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
0answers
24 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 ...
0
votes
1answer
29 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 ...
-5
votes
0answers
23 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
42 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

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?
9
votes
2answers
1k views

Does this article imply that Turing-Computability is not the same as “effectively computable”?

I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve. In my understanding, this should mean, intuitively, that this problem is "effectively ...
0
votes
1answer
35 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
49 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
27 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
2answers
113 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 ...
2
votes
1answer
44 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 ...
4
votes
1answer
67 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.
3
votes
2answers
6k views

Showing that deciding whether a given TM accepts a word of length 5 is undecidable

I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this: Assume that $M_5$ is a Turing Machine that can decide if a given Turing Machine $M$ accepts ...
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 ...
0
votes
1answer
66 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 ...
1
vote
0answers
118 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
48 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 ...
1
vote
1answer
172 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?
2
votes
0answers
35 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 ...
2
votes
2answers
205 views

Turing Machine - Analyze brackets

For a practical task, we are asked to provide the transition table for a Turing machine that validates the number of open brackets is equal to the number of closing brackets. The only tape symbols ...
0
votes
1answer
145 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?
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
36 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
176 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
3answers
78 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 ...
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
2answers
7k views

Intersection/Union of recursively enumerable languages that aren't decidable?

For $L_1,L_2 \in RE - R $ , I want to prove or disprove if the following can occur: $L_1 \cap L_2 \in R$ $L_1 \cup L_2 \in R$ $L_1 \cap L_2 \in R$ and $L_1 \cup L_2 \in R$ What I did: I think any ...
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 ...
2
votes
1answer
31 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
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
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)$, ...
2
votes
1answer
55 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 ...
1
vote
1answer
24 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
52 views

What is the contradiction in the proof of the halting theorem?

In the standard proof of the halting theorem, you are asked to assume that a TM_0() exists that takes another TM_1() and a string W and outputs whether TM_1() halts or executes forever right on string ...
2
votes
0answers
335 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 ...
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
1answer
168 views

How to translate automaton (Turing machine) into the program of high level programming language?

Every program in high level ("industrial") programming language can be expresses as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian ...
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 ...
0
votes
1answer
52 views

Undecidability of TMs recognizing a decidable language

The language $L = \{ \text{M} \mid \text{M is a TM and the set of words w such that M halts on w is decidable} \}$ is given. I need to prove that $L$ is NOT Turing recognizable. I've got a hint: it ...

1
2 3 4 5
40