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
64
votes
6answers
15k 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 ...
30
votes
7answers
8k 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. ...
12
votes
3answers
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) ...
63
votes
11answers
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 ...
13
votes
1answer
7k 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 ...
50
votes
2answers
38k 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
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 ...
11
votes
3answers
804 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?
18
votes
3answers
9k 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?
12
votes
6answers
34k 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 ...
3
votes
2answers
7k 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. ...
19
votes
1answer
3k 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 ...
8
votes
3answers
595 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
87 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: 𝑆 β†’ π‘Žπ‘† | π‘Žπ‘… 𝑅 β†’ 𝑏𝑅 | 𝑏𝑇 𝑇 β†’ 𝑐𝑇...
26
votes
5answers
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 ...
4
votes
4answers
9k 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 ...
8
votes
1answer
17k 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 ...
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
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 ...
3
votes
1answer
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$? ...
11
votes
3answers
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 ...
3
votes
3answers
823 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 ...
61
votes
7answers
24k 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. ...
27
votes
4answers
15k 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$ ...
32
votes
2answers
6k 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-...
31
votes
2answers
9k 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 ...
52
votes
2answers
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 ...
30
votes
7answers
25k 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 ...
6
votes
1answer
11k 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 ...
24
votes
4answers
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 ...
9
votes
4answers
10k 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 ...
9
votes
2answers
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)? ...
5
votes
4answers
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 ...
3
votes
2answers
10k 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
14k 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 $...
20
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 ...
5
votes
1answer
5k views

Proving ALLTM complement not recognizable

A few definitions.. $$ \begin{align*} \mathrm{ALL}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) = \{0,1\}^{*} \Bigr\} \\[2ex] \...
3
votes
1answer
641 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 ...
3
votes
1answer
1k views

Right moving turing machines and FSA's

I stumbled upon the following post while learning about turing machines: Right moving turing machine I kind of understand the intuition behind why a TM that only moves to the right works like a FSA ...
2
votes
1answer
589 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 ...
2
votes
2answers
6k 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
3k 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. ...
7
votes
2answers
305 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
292 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
1k 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
255 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 ...
35
votes
5answers
15k views

What does being Turing complete mean?

I see that most definitions of what it is to be Turing-complete are tautological to a degree. For example if you Google "what does being Turing complete mean", you get: A computer is Turing ...
32
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 ...
15
votes
3answers
21k views

Why is this true: β€œThere are countably many Turing Machines” [duplicate]

It is said that there are uncountably many languages but only countably many Turing Machines. Could someone make this clear to me? And this doesn't mean that the set of TM is finite, yes?

1
2 3 4 5 6