# Questions tagged [turing-machines]

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

1,603 questions
Filter by
Sorted by
Tagged with
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 ...
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?$
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 ...
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 ...
253 views

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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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}. ...
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 ...
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 ...
586 views

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 ...
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 ...
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 $... 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 ... 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 ... 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 ... 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 ... 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) =$... 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 ... 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 ... 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,... 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? 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 ...