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
10
votes
3answers
869 views

Decidable languages and unrestricted grammars?

Turing machines and unrestricted grammars are two different formalisms that define the RE languages. Some RE languages are decidable, but not all are. We can define the decidable languages with ...
5
votes
2answers
523 views

Proof-sketch on the language accepted by a Turing machine

Let $T$ be a Turing machine whose accepted language is $L(T)$. Let $X$ be another language. How do you approach a proof like $L(T)\subseteq X?$
9
votes
2answers
454 views

A variant of the busy beaver function

Reading this question "Natural RE undecidable problems but not Turing-complete" the following language came to my mind: If $\Sigma(\cdot)$ is the busy beaver function (maximum attainable score among ...
7
votes
2answers
3k views

Non-deterministic Turing machine that halts on at least one branches of computation

I'm looking at my textbook here from Michael Sipser and he says that a nondeterministic Turing machine is a decider if all its computation branches halt on all inputs. I think I recall seeing ...
4
votes
2answers
253 views

Intuition about decidability

Given a language, how do you go about deciding if it's decidable or not? For example: Given a DFA $A_0$ and a TM $M_0$ $L_1 = \{ \langle M \rangle \, | \, M \mbox{ is a TM and }L(M) = L(A_0) \}$ $...
7
votes
3answers
636 views

Meaning of the Halting problem

The Halting Problem is defined as: $H_{TM} = \{ \langle M, w \rangle \mid \text{\(M\) halts on input \(w\)}\}$ I'm not sure what it means. Is $H_{TM}$ a collection of Turing Machines such that all ...
6
votes
2answers
793 views

Mapping reductions for dummies

I am having trouble understanding a mapping reduction and I would appreciate your help. Define $\quad \begin{align} A_{TM} &= \{ \langle M, w \rangle \mid M \text{ Turing machine}, w \in \...
28
votes
2answers
5k views

Why are there more non-computable functions than computable ones?

I'm currently reading a book in algorithms and complexity. At the moment I'm, reading about computable and non-computable functions, and my book states that there are many more functions that are non-...
13
votes
3answers
4k views

P, NP and specialised Turing Machines

I'm sort of new, but very interested to the field of computing and complexity theory, and I want to clarify my understanding about how to class problems, and how strongly the problems relate to the ...
3
votes
2answers
601 views

Show that the Turing Machine domain can be viewed as a classical planning domain

This is one of my assignments. I am not able to comprehend how to reduce the Turing machine domain to Classical planning domain. My understanding is that we have to essentially perform complexity ...
4
votes
4answers
547 views

Can Turing Machines solve non-decision problems?

Since TMs are equivalent to algorithms, they must be able to perform algoriths like, say, mergesort. But the formal definition allows only for decision problems, i.e, acceptance of languages. So how ...
26
votes
5answers
22k views

Practical importance of Turing machines?

I am an electrical engineer, and only had one CS course in college 26 years ago. However, I am also a devoted Mathematica user. I have the sense that Turing Machines are very important in computer ...
0
votes
1answer
848 views

Time complexity of generating the first n primes and their product

Suppose that I have a turing machine that receives as input the string $1^{n\times n}$ (unary input), what is the time complexity of writing $p_1,...,p_n$ on the output tape, where $p_i$ is the i-th ...
0
votes
1answer
77 views

Are you allowed to have empty states on Turing machine?

So I'm doing some exercises with Turing machine and quite often it happens that a given set of states can be achieved if and only if some character was met. Therefore, we may have some states q3-q7 ...
0
votes
1answer
61 views

Clarification for a class of Turing machine problems

So say I have a task like this: Construct a Turing machine transforming the word u to the word v byt removing all the sequences of form "ba" from the word u. Input alphabet = {a,b,c}. ...
7
votes
3answers
6k views

What is the difference between a TM accepting and deciding a language?

Frankly I'm very uncomfortable with the material right now. There are some things I can understand, but many I still do not. My first assignment is asking me in one question (which I do know how to ...
4
votes
5answers
181 views

Where can I find a short and 'easy' peer reviewed paper on something from computability, decidability or complexity?

It's a homework assignment, we were asked to read, understand, and present to our colleagues a short paper/article (suggested 4-6 pages) for our Computability, Decidability or Complexity class. The ...
6
votes
3answers
586 views

Is there a single valid definition for a Turing Machine, or is it mutable?

I'm just learning about Turing Machines, and I'm a bit confused by the difference in formal description between Wikipedia and my textbook. My textbook says the following: $$M=\langle Q,\Sigma,\Gamma,...
10
votes
0answers
769 views

Universal Turing Machine simulation with bounded time overhead

Is it possible to design a Universal Turing Machine in which the simulation time of a given Turing Machine $M$ is bounded by a factor of $\mathcal{O}(\log|\Gamma|+\log|Q|)$ of the original running-...
7
votes
2answers
309 views

Faster growing busy beaver function

Standard busy beaver function draws attention to final count of nonzero symbols on tape. We could instead look at largest amount of nonzero symbols appearing on tape at any point of computation. This ...
2
votes
1answer
306 views

How to prove “The power set of a countable set must be uncountable”?

I'm not sure if this statement is correct, but my friend said so. The problem arose from this T/F question: Let $F=\{f: f$ be a primitive recursive function from $\mathbb{N}$ to $\mathbb{N}\}$, then $...
-2
votes
3answers
457 views

If set of TM's is not countable?

I was reading about counting principle related to TOC. I understand that the set of TMs are countable infinity. I couldn't understand the significance of it. What is its not countable?
1
vote
1answer
122 views

Design the transition function

I need to design a Turing Machine that accepts the (context-free) language: $L(M)=\{0^{n}1^{n+1}: n\ge1$}. $$Q=\{q_0,q_1,q_2,q_3,q_4\} ,Σ = \{0,1\}, Γ =\{0,1,X,Y,B\}, F=\{q_4\}$$ X- processed 0 Y- ...
7
votes
3answers
321 views

Is there a simple example of sets such that $A \leq_T B$ but not $A \leq_m B$?

I wonder if there is a simple example of sets $A$ and $B$ such that $A$ is Turing-reductible to $B$ but not many-to-one reductible to $B$.
5
votes
1answer
942 views

Decision problem and algorithm

I was reading about decision problem. I understand that decision problem tell yes/no answer for an input. The decision is based on a decision procedure also called an algorithm. The wikipedia says ...
4
votes
3answers
2k views

Turing machine and coming up with an idea

I read many things about the Turing machine and understand how it works but what I can't get the grasp of (and what none of the books seem to try to teach) is how should I approach a problem I am ...
0
votes
1answer
1k views

Standard notation for the language of the universal Turing machine?

The universal Turing machine $U_{TM}$ is a TM that takes in as input an encoding of a TM and a string, then runs the TM on the string and does whatever the simulated TM does. The language of the ...
9
votes
2answers
582 views

Why are computable numbers (in Turing's sense) enumerable?

Why are computable numbers (in Turing's sense) enumerable? It must be very obvious, but I'm currently just not seeing it.
1
vote
1answer
559 views

alphabet of a single tape turing machine that simulates a multitape TM

First of all sorry, if this question already exists, in that case, pointing to the right direction will be appreciated. Secondly, sorry, if the question is below the expected level of Niveau, but all ...
23
votes
6answers
30k views

Recursive and recursively enumerable language definition for a layman

I've come across many definitions of recursive and recursively enumerable languages. But I couldn't quite understand what they are . Can some one please tell me what they are in simple words?
0
votes
3answers
156 views

Looking for some more details on “Turing” devices

I've been reading a lot of computer science literature in the recent past but haven't ran across an explanation of Turing machines, the different types, and why they seem to come up so often (I ...
2
votes
2answers
3k views

How can I prove that the language of a read-only Turing machines is regular?

I find this, but I can't complete it, is there any other solution for it?
1
vote
1answer
177 views

How come this turing machine running time is $O(n^{1+\log_2 2006}\cdot \log_2n)$

Given a deterministic Turing machine with an input tape and a work tape. The work tape is restricted to $\log_2 n+100$ cells ($n$ represents the input length) and its tape alphabet is of size $2006$. ...
15
votes
6answers
3k views

Can there be a perfect chess algorithm?

Current chess algorithms go about 1 or maybe 2 levels down a tree of possible paths depending on the player's move's and the opponent's moves. Let's say that we have the computing power to develop an ...
2
votes
3answers
1k views

Undecidability of the following language

So we can prove that the language say $A = \{ \langle M,w \rangle \mid \text{M is TM that accepts } w^R \text{ whenever it accepts } w \}$ is undecidable by assuming it is decidable and use that to ...
16
votes
1answer
381 views

An interesting metric space related to Turing machines

In this question we only consider Turing machines that halt on all inputs. If $k \in \mathbb{N}$ then by $T_k$ we denote the Turing machine whose code is $k$. Consider the following function $$s(x,...
3
votes
1answer
688 views

Speed-up of two-tape Turing machine

I try to figure out linear speed-up of Turing machine. Prove that any problem that can be solved by a two-tape Turing machine that has time complexity t can be solved by another two-tape Turing ...
2
votes
1answer
617 views

Solvability of Turing Machines

I'm preparing for an exam, and on a sample one provided (without solutions), we have this question: Is the following solvable or non-solvable: Given a turing machine $T$, does it accept a word of even ...
7
votes
1answer
208 views

Does forcing TMs to change all symbols they read change their power?

If we limit a turing machine so that it is not allowed to write the symbol that it reads would it reduce its power? For example: $( State, A, State, Z, DIRECTION)$ $A$ cannot be the same symbol as $...
2
votes
2answers
186 views

Reducing recursive languages

I need a clarification related to the following situation. Consider a Turing machine $T_1$ that halts for every input. In other words $J_1 = L(T_1) \subseteq \Sigma^*$ is recursive. Suppose we are ...
1
vote
1answer
1k views

How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$: Write a ...
2
votes
1answer
2k views

Show the Language is Recursive

I have devised the following TM for the language EQUAL. EQUAL accepts all strings with the same number of a's and b's. It is context free but non regular. Using the TM I devised, how can I show ...
6
votes
1answer
1k views

Why is it that every k-tape Turing machine has a 1-tape TM that runs in $O(t^2(n))$?

Apparently, for every k-tape Turing machine that runs in time $O(t(n))$, there exists a 1-tape Turing machine that runs in $O(t^2(n))$. I can see how any multi-tape machine $M$ can be simulated by a ...
5
votes
1answer
186 views

Conflicting definitions of language accepted by Turing Machine?

I am reading Papadimitriou, Computational Complexity, page 24, where it is says We say that $M$ accepts $L$ whenever for any string $x \in (\Sigma - \{\sqcup\})^*$, if $x \in L$, then $M(x) =$ ``...
2
votes
1answer
255 views

Question about a semi-decidable property of languages

Consider the following property of recursively enumberable (RE) languages $$ L = \{ J \in \text{RE} \mid J \cap L_{uni} \ne \emptyset \}$$ where $L_{uni}$ is the language of the Universal Turing ...
12
votes
1answer
2k views

Gödelization in Turing Machine

I was looking at Gödelization in Theory of Computation course. I could understand the Gödel numbering concepts, but couldn't understand its importance in Theory of Computation. Could anyone please ...
2
votes
2answers
12k views

How to draw a Turing Machine for Even-Even

A TM to accept EVEN-EVEN (a collection of all strings with an even number of a's and an even number of b's) can be based on the algorithm: Move up the string, changing a’s to A’s Move down the string,...
6
votes
1answer
342 views

Prove multiple cell move instructions don't increase power of Turing Machines

How can you prove that multiple-cell-move instructions, for example (X, Y, 5R) and (X, Y, 17L), do not increase the power of a Turing Machine?
3
votes
1answer
174 views

Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$?

I have a book that proves the halting problem with this simple statement: $$ A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon $$ It states that halting problem reduces to the ...
7
votes
2answers
348 views

Mathematical model on which current computers are built

It is said that "The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists ...