# Questions tagged [turing-machines]

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

283 questions
Filter by
Sorted by
Tagged with
17k views

### Are there minimum criteria for a programming language being Turing complete?

Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete? From what I can tell from wikipedia, the language needs to ...
9k views

### What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
2k views

### Why can't we flip the answer of a NDTM efficiently?

I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) ...
12k views

### Human computing power: Can humans decide the halting problem on Turing Machines?

We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines ...
8k views

### Single-tape Turing Machines with write-protected input recognize only Regular Languages

Here is the problem: Prove that single-tape Turing Machines that cannot write on the portion of the tape containing the input string recognize only regular languages. My idea is to prove that this ...
40k views

### Is a push-down automaton with two stacks equivalent to a turing machine?

In this answer it is mentioned A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is ...
1k views

### Universal simulation of Turing machines

Let $f$ be a fixed time-constructable function. The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given the description of ...
852 views

### References on comparison between quantum computers and Turing machines

I was told that quantum computers are not computationally more powerful than Turing machines. Could someone kindly help in giving some literature references explaining that fact?
10k views

### Is there any uncountable Turing decidable language?

There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?
36k views

### Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?

Let $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$ Is there a Turing machine R that decides (I don't mean recognizes) the language $L_\emptyset$? It ...
8k views

### Prove Queue Automaton is equivalent to Turing Machine

A deterministic queue automaton (DQA) is like a PDA except the stack is replaced by a queue. A queue is a tape allowing symbols to be written (push) on the left-end and read (pull) on the right-end. ...
4k views

### How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?

According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows ...
618 views

### Can the encodings set of a non-trivial class of languages which contains the empty set be recursively enumerable?

Let $C$ be a non-trivial set of recursively enumerable languages ($\emptyset \subsetneq C \subsetneq \mathrm{RE}$) and let $L$ be the set of encodings of Turing machines that recognize some language ...
966 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 ...
93 views

### Is it possible for a Turing machine to be able to reduce a grammar and tell where it fits in chomsky hierarchy?

For example: This looks like a context free grammar: 𝑆 → 𝑄𝑅𝑇 𝑄 → 𝑎𝑄 | 𝑎 𝑅 → 𝑏𝑅 | 𝑏 𝑇 → 𝑐𝑇 | c but it can be reduced to this regular language: 𝑆 → 𝑎𝑆 | 𝑎𝑅 𝑅 → 𝑏𝑅 | 𝑏𝑇 𝑇 → 𝑐𝑇...
8k views

### Why are functional languages Turing complete?

Perhaps my limited understanding of the subject is incorrect, but this is what I understand so far: Functional programming is based off of Lambda Calculus, formulated by Alonzo Church. Imperative ...
10k views

### Language of Turing machines that loop on all inputs, recognizable?

Prove that the language Loop Turning Machine = { < M > | M is a TM that loops on all inputs} is recognizable. I feel like $M$ would never halt. To make $M$ recognizable it needs to accept or ...
18k 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 ...
3k views

### Are turing machine really countable?

I feel the notion "there are countably many Turing machines" is wrong. Suppose there is a Turing machine whose input alphabet is {0}. If we replace the input alphabet {0} with {a} and replace every ...
3k views

### Show that Halting problem $(\mathsf{HP\text{}})$ is $\mathsf{NP\text{-}Hard}$

Let me define first Halting problem $(\mathsf{HP\text{}})$. Given : $(M , x)$, $M$ is a turing machine and $x$ is a input binary string to turing machine $M$. Decide : Does $M$ halt on string $x$? ...
2k views

### Is regularity of the language accepted by a given Turing machine a semi-decidable property?

Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of ...
1k 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 ...
26k views

### Is a Turing Machine "by definition" the most powerful machine?

I agree that a Turing Machine can do "all possible mathematical problems". But that is because it is just a machine representation of an algorithm: first do this, then do that, finally output that. ...
10k views

### What is the difference between quantum TM and nondetermistic TM?

I was going through the discussion on the question How to define quantum Turing machines? and I feel that quantum TM and nondetermistic TM are one and the same. The answers to the other question do ...
7k 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-...
7k views

### How to define quantum Turing machines?

In quantum computation, what is the equivalent model of a Turing machine? It is quite clear to me how quantum circuits can be constructed out of quantum gates, but how can we define a quantum Turing ...
26k 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 ...
12k 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 ...
1k views

### Do undecidable languages exist in constructivist logic?

Constructivist logic is a system which removes the Law of the Excluded Middle, as well as Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't ...
11k views

### Does our PC work as Turing Machine?

Does our PC work as Turing Machine? The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have ...
4k views

### Infinite alphabet Turing Machine

Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)? ...
4k views

### Is there an example of a recursive language which is not context sensitive?

I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^*$ is prototypical of regular languages, $a^nb^n$ for ...
2k views

### How is the computational power of a human brain comparing to a turing machine?

This seems related to these questions at a glance: What are some problems which are easily solved by human brain but which would take more time computers? What would show a human mind is/is not ...
11k views

### Counters in Turing machines

I know how a Turing machine works, how it accepts a language but in some. In some scenarios we would like to use counters. For example, I want to develop a machine that accepts $\{0^{2n} : n \geq 0\}$...