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

learn more… | top users | synonyms

1
vote
1answer
15 views

Universal Turing machine

I'm trying to find the answers of two questions about the Universal Turing machine. 1.How can the Universal Turing machine simulate a Turing machine if the one that is being simulated has a bigger ...
2
votes
0answers
22 views

Why would $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $

I was reading the following paper by Jim Kadin, "$P^{NP[O(\text{log } n)]}$ and sparse Turing complete sets for NP" The main result is that if there is a sparse set $S \in NP$ such that $coNP ...
0
votes
1answer
37 views

Turing Machines and Algorithm for Language Acceptance

Is there an algorithm to decide if any two Turing machines accept the same language? I can't find a definite answer to this. My guess is that there isn't, because then we would be able to decide if ...
-1
votes
1answer
18 views

NDTM for Graph Clique Problem in poly-time

I am having a doubt. This is my NDTM algorithm: GCP(G, k): generate a list with k distinct nodes from graph G generate an adjacency matrix, fill it with 1 if an edge exist, 0 otherwise check if ...
0
votes
1answer
33 views

How does a turing machine with doubly infinite tape simulate a normal-taped turing machine?

The intuition is that on any input, we can write a symbol like $\#$ on the left that tells the machine to not move past this symbol. However, I'm running into problems trying to show this using the ...
1
vote
2answers
62 views

Non-erasing Turing machines and loss of generality

A non-erasing Turing machine is one that cannot replace a symbol with a blank unless the symbol under the read head is a blank. I'm trying to understand whether there is loss of generality because of ...
3
votes
1answer
26 views

Non-deterministic vs Deterministic turing machine to solve graph colouring

For graph coloring decision problem I mean the following: given a undirected graph, $G$, we have $GCDP(G, n)$. This returns yes instance is given if it we can color the graph with n different colors. ...
0
votes
0answers
13 views

Forward jump turing machine and r.e languages [duplicate]

I was going through some exercises I found online and I am really stuck at this problem: Consider Turing Machines with the following restriction: they are only allowed forward jumps, i.e. if ...
2
votes
3answers
61 views

Turing machine for unary encoded quadratic numbers

I want to design a turing machine that accepts strings of the form $0^{n^2}$ where $n \geq 1$ and I want to give an implementation description for this. So I am thinking that the algorithm can go ...
-2
votes
1answer
18 views

Quadratic lower bound for deciding the set of palindromes

How to prove a single tape Turing machine needs at least n squared time to decide palindrome? This is an exercise from the "computational complexity - a modern approach" book.
-1
votes
0answers
27 views

Turing machine that takes in $0^a 1^b 2^c$ where $0\le a\le b\le c$

I need to describe a Turing machine that accepts strings of the form $0^a 1^b 2^c$ where $0\leq a \leq b \leq c$ and I can use multiple tapes if I want to. I just can't come up with one for this. I ...
-2
votes
0answers
15 views

Is quantum Turing recognizability/decidability bigger than (classical)Turing-recognizability/decidability?

How does the set of quantum-Turing recognizable languages compare to the set of Turing recognizable languages? Same question for decidability. Is the former strictly more powerful than the latter?
0
votes
1answer
23 views

How do I manage flow control with no ELSE statement? (on Turing machine)

I have been given the problem of writing a turing machine with the commands: if, while, whileNot, read X, write X, goLeft, goRight, HALT The problem was simply ...
1
vote
1answer
38 views

If A is decidable and B is decidable, then A is Turing Reducible to B

The statement seems intuitively true but is it? If so, how can I prove this?
0
votes
0answers
27 views

P-time reduction A < B where B has no no-instance

I had a question to prove whether a reduction can exist $A < B$, if B has no no instances and one yes instance. I am not sure if this is too trivial. Let $A \in P$ and $Y$ be the only yes-instance ...
1
vote
0answers
59 views

A complete catalog of 2-state Turing machines?

For educational purposes, I'm about to start a research project that involves creating a complete database documenting and classifying all 2-state, 2-symbol Turing machines, according to a ...
0
votes
1answer
23 views

Halting problem reduction to Halting for all inputs

I was going through my book of revision and I would like someone hints on this. The Halt for All Input problem (HAI) takes a machine and tell if this machine halts or not for any input We prove it ...
0
votes
1answer
32 views

Halting problem reducing to the blank tape halting problem

I was going through my book of proof and I find very confusing its definition, so I would like someone to help me in understanding this. The blank tape problem takes a machine and an empty tape and ...
3
votes
2answers
82 views

Halting Problem and Turing Degree and Reduction? [closed]

This is a Local Olympiad question on computation and computer science on 2013. How can explain it and says some hint for understanding such an example question. for $ A \subseteq \mathbb{N}$ we ...
1
vote
3answers
58 views

Language is recursive, hence recursively enumerable

I was going through a book of proof and I read: If L is recursive, L is r.e. And the proof goes: Let L be recursive, hence there is a TM that decides it Convert an halt state to a normal state ...
2
votes
1answer
64 views

Turing recognizable -decidable languages-

I was wondering how to prove that $C$ (which is a language) is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$. I do not ...
2
votes
1answer
40 views

Can a probabilistic Turing Machine compute an uncomputable number?

Can a probabilistic Turing Machine compute an uncomputable number? My question probably does not make sense, but, that being the case, is there a reasonably simple formal explanation for it. I should ...
3
votes
1answer
37 views

Why are there $(2kn+1)^{kn}$ Turing Machines with $k$ symbols and $n$ states?

I've seen a few references [1], [2], [3] that say that for a Turing Machine with transition function defined by: $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$ the number of ...
-1
votes
0answers
32 views

Counting the number of strings generated by a TM

I'm having an issue with the following exercise (roughly translated by me); Given a turing machine $A$, which generates strings over a certain alphabet, and a turing machine $B$ which accepts a ...
6
votes
1answer
156 views

What is the relationship between Turing Machines with a finite tape and Finite State Automata?

I seem to recall from an undergraduate class that for a Turing Machine with a finite tape there will always exist a corresponding Finite State Automata, but I've been unable to find this confirmed ...
0
votes
1answer
43 views

Is a partial function Turing-computable?

From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and ...
0
votes
1answer
104 views

Proving a language is not Turing-recognizable by reduction

I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment. I need to prove a language L is not ...
1
vote
1answer
84 views

Is the following statement about turing machines true?

Here's the statement: Take a set of finite inputs from some alphabet. If for any two turing machines: All inputs in the set produce the same output for both machines In both machines, ...
1
vote
2answers
48 views

Is it true, If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?

If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive? If it is true how to prove it? Update It is my attempt, If $A$ is turing recognizable (r.e.) and $\bar{A}$ is r.e. then ...
1
vote
3answers
118 views

Examples of processes / problems that cannot be tackled by Turing Machines

I know that there are problems that cannot be solved by any algorithm, such as the Halting problem. I also know that some processes cannot be even adequately approximated by any Turing Machine ...
0
votes
1answer
145 views

PDA with N-Stacks comparison with Turing Machines [duplicate]

Is it possible to compare PDA having N-Stacks with Turning Machines. Are they equally powerful in this situation? It's been told that PDA with 2-Stacks is equally powerful to Turning Machine. But ...
0
votes
0answers
78 views

Is the language of Turing Machines that halt on every input recognizable?

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
0
votes
0answers
32 views

Designing a turing machine to determine if there is path from two vertices in a directed graph or not

I'm self studying automata and I'm in chapter 7 of Sipser book. I want to design a diagram for a Turing machine that shows if there is path from s to t in a directed graph. My tape is like this: ...
0
votes
1answer
33 views

How to design a Turing Enumerator which either ends with 011 or is of odd length? [closed]

This question was asked by my professor in optional brain teaser section, I have tried to solve it for last 48 hours, I am not able to construct a deterministic Turing Machine, Can someone provide ...
1
vote
0answers
28 views

Decidable non time constructible function

Can anyone help me find an example of a function $f:\mathbb{N}\rightarrow\mathbb{N}$ which satisfies $\forall n\in\mathbb{N}: f(n)\ge n$ and is decidable, i.e. there exists some Turing machine $M_f$ ...
4
votes
2answers
1k views

What is 'halting'?

I've read a definition that says that "co-semi-decideable' means that a TM is halting on all inputs NOT in the language. I've heard the word come up a lot, and I've so far assumed that halting just ...
3
votes
1answer
86 views

I/O in Theory of Computation

I posted a question "Arbitrary Programs that halt" some days ago and now i think my doubt is a lot more clear. I concluded that in any arbitrary program that halts, control flow operations, ...
0
votes
2answers
49 views

Turing Machines: Arbitrary alphabet equivalence with binary alphabet

Think of an $n$-ary alphabet as $\{0, 1, ..., n-1, n\}$. For example, a binary alphabet is $\{0, 1\}$. Do Turing Machines with binary alphabets decide the same set of languages as Turing Machines ...
3
votes
1answer
76 views

Arbitrary Programs that Halt

I've been learning about Theory of Computation lately, and i'm trying to link general programming with the Theory of Computation. I thought of considering any arbitrary program that halts, as an ...
0
votes
1answer
52 views

Proving that it's decidable whether a TM ever moves on the blank input

I'm trying to understand how to prove a language is decidable, semi-decidable, co-semi-decidable, or none of the above. I've got the problem: $$A_{\mathrm{right}} = \{ \left< M\right> | M ...
2
votes
2answers
40 views

will this be decidable or partially decidable?

$A=\{\langle M \rangle \mid M \text{ is a turing machine and }|L(M)|\geq3\}$ Since Recursive enumerable languages are turing enumerable, so listing of all strings of the language in finite time is ...
3
votes
1answer
52 views

Are there criteria that will make: $A \subseteq B$, $A$ unrecognizable imply $B$ unrecognizable?

Let $A \subseteq B$, and A is unrecognizable. I know in general that doesn't mean B is unrecognizable. However, are there some limitations we could put on A and B that would make it true? The only ...
0
votes
0answers
23 views

Can we write algorithms without conditional statements? [duplicate]

Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional. Consider the factorial problem, we would typically define ...
1
vote
1answer
61 views

Is $T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$ recognizable?

$$T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$$ I started with Rice's theorem (come up with an example where $|L(M)| = 2$) to see that $T$ was undecidable. Then I figured out ...
5
votes
4answers
855 views

Can we write algorithms without conditional statements?

Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional. Consider the factorial problem, we would typically define ...
2
votes
1answer
23 views

Looking for an example of proving space upper bounds for computing functions on a DTM

Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of ...
0
votes
1answer
23 views

How to prove computational completeness of a variant of P system

I have read a lot of books on membrane computing (P system), of which the computational completeness of several variants are already under investigation. My goal is to design my own variant and prove ...
5
votes
1answer
100 views

Combinational Logic Circuits and Theory of Computation

I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything i have learned recently in Theory of Computation. I was thinking whether combinational ...
0
votes
0answers
41 views

Are all Turing machines recognizable? [duplicate]

Is the language of the set of descriptions of all Turing machines recognizable? I'm thinking not, but I can't quite define why. A language is Turing-recognizable if some Turing machine recognizes ...
2
votes
1answer
131 views

Language consisting of all Turing machine encodings [closed]

$A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ } What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL? I would say $A$ is decidable since we can write an algorithm to check ...