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
54
votes
6answers
11k 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 ...
27
votes
7answers
6k 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. ...
10
votes
3answers
1k 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) ...
59
votes
10answers
10k 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 ...
11
votes
2answers
5k 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 ...
39
votes
1answer
26k 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 ...
16
votes
1answer
926 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 ...
11
votes
3answers
625 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?
11
votes
6answers
23k 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 ...
8
votes
3answers
460 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 ...
1
vote
1answer
74 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: ๐‘† โ†’ ๐‘Ž๐‘† | ๐‘Ž๐‘… ๐‘… โ†’ ๐‘๐‘… | ๐‘๐‘‡ ๐‘‡ โ†’ ๐‘๐‘‡...
16
votes
3answers
6k 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?
4
votes
4answers
7k 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 ...
6
votes
3answers
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 ...
3
votes
1answer
880 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$?...
3
votes
2answers
5k 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. ...
18
votes
1answer
2k 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 ...
2
votes
1answer
1k 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 ...
9
votes
3answers
852 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 ...
51
votes
7answers
20k 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. ...
51
votes
2answers
6k 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 ...
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-...
8
votes
4answers
7k 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 ...
4
votes
1answer
6k 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 ...
9
votes
2answers
3k 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)? ...
6
votes
1answer
12k 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 ...
5
votes
2answers
910 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 ...
3
votes
2answers
6k 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\}$...
3
votes
3answers
11k views

Construct Turing Machine which accepts the language $ww$

I try to construct a TM that accepts the language $\{ ww \mid w \in \{a,b\}^* \}$. Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second $...
17
votes
4answers
2k views

Defining the halting problem for non-deterministic automata

The primary definition of Turing machine (TM), at least in my own reference textbook (Hopcroft+Ullman 1979) is deterministic. Hence my own understanding of the halting problem is primarily for ...
3
votes
1answer
303 views

Construction of the complement of universal Turing machine - where is the catch?

This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{u}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct ...
2
votes
2answers
4k views

Is the language TMs that accept finite languages Turing-recognizable?

I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable? What I ...
2
votes
1answer
353 views

Power of variants of Turing machines

I'm having trouble with this problem as I haven't discovered a good way to determine the power of a Turing machine. I was under the impression that if a Turing machine can perform the same actions ...
1
vote
1answer
2k views

Right moving turing machine

I am interested in simulating any turing machine with a turing machine that is allowed only to move right. I guess that it should be pretty standard material and likely it is trivial (or known to be ...
16
votes
2answers
2k views

Decidablity of Languages of Grammars and Automata

Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2. Here are the two questions I'm looking at from a past exam. ...
6
votes
2answers
257 views

Is there an always-halting, limited model of computation accepting $R$ but not $RE$?

So, I know that the halting problem is undecidable for Turing machines. The trick is that TMs can decide recursive languages, and can accept Recursively Enumerable (RE) languages. I'm wondering, is ...
4
votes
3answers
247 views

Splicing squares on a Turing Machine finite tape

Trying to explain a problem, I thought of a variant of Turing Machines. It is unlikely to be new, but I do not recall ever seing it before, and I wonder whether it has been used or has a name. The ...
3
votes
1answer
850 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 ...
2
votes
2answers
143 views

Oracle Relations Between Complexity Classes

I'm trying to get a better handle on oracle separations between complexity classes but I keep running up against some (seemingly) silly issues that make me think that I'm fundamentally ...
2
votes
1answer
119 views

Which one of these two sets is computably enumerable?

M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language. {M : |L(M)| <= 330} {M : |L(M)| >= 330} I don't quite understand what this question is asking. ...
24
votes
4answers
12k views

Proof of the undecidability of the Halting Problem

I'm having trouble understanding the proof of the undecidability of the Halting Problem. If $H(a,b)$ returns whether or not the program $a$ halts on input $b$, why do we have to pass the code of $P$ ...
30
votes
7answers
2k views

Is there a connection between the halting problem and thermodynamic entropy?

Alan Turing proposed a model for a machine (the Turing Machine, TM) which computes (numbers, functions, etc.) and proved the Halting Theorem. A TM is an abstract concept of a machine (or engine if ...
21
votes
5answers
6k 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 ...
26
votes
5answers
21k 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 ...
8
votes
4answers
3k views

How does a nondeterministic Turing machine work?

What is differences between deterministic and nondeterministic Turing machines? Different but equivalent models of NDTM. In particular, what is this frequently used phrase "nondeterministically guess"?...
23
votes
6answers
5k views

Can input to a Turing machine be of infinite length?

Considering only the alphabet $\Sigma = \{0,1\}$, the strings which can be given as input to the Turing machines are from the set $\Sigma^{*}$. But does it make sense for the input to be an infinite ...
21
votes
4answers
3k views

Does a never-halting machine always loop?

A Turing machine that returns to a previously encountered state with its read/write head on the same cell of the exact same tape will be caught in a loop. Such a machine doesn't halt. Can someone ...
18
votes
2answers
332 views

Problems that provably require quadratic time

I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$. The problem needs to have the following properties: $\Omega(n^2)$ runtime proof for any algorithm - ...
9
votes
1answer
1k views

Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
6
votes
6answers
1k views

How is it valid to use oracles in mathematical arguments?

Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle". Thus, Oracles do not exist almost by ...