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
67
votes
6answers
14k views

Why is the Turing Machine a popular model of computation?

I am a CS undergraduate. I understand how Turing came up with his abstract machine (modeling a person doing a computation), but it seems to me to be an awkward, inelegant abstraction. Why do we ...
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 ...
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 ...
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 ...
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 ...
37
votes
4answers
8k views

Theoretical machines which are more powerful than Turing machines

Are there any theoretical machines which exceed Turing machines capability in at least some areas?
32
votes
5answers
13k 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 ...
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 ...
28
votes
2answers
4k views

Church-Turing Thesis and computational power of neural networks

The Church-Turing thesis states that everything that can physically be computed, can be computed on a Turing Machine. The paper "Analog computation via neural networks" (Siegelmannn and Sontag, ...
28
votes
4answers
4k views

What did Turing mean when saying that “machines cannot give rise to surprises” is due to a fallacy?

I encountered below statement by Alan M. Turing here: "The view that machines cannot give rise to surprises is due, I believe, to a fallacy to which philosophers and mathematicians are ...
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-...
28
votes
2answers
6k 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 ...
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. ...
26
votes
6answers
5k views

Is there a physical analogy to the Turing Machine?

Recently in my CS class I've been introduced to the Turing Machine. After the class, I spent over 2 hours trying to figure out what is the relationship between a tape and a machine. I was ...
26
votes
5answers
33k views

Difference between a turing machine and a finite state machine?

I am doing a presentation about Turing machines and I wanted to give some background on FSM's before introducing Turing Machines. Problem is, I really don't know what is VERY different from one ...
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 ...
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$ ...
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 ...
23
votes
6answers
29k 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?
22
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 ...
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 ...
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 ...
21
votes
1answer
5k views

Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?

In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also ...
20
votes
5answers
4k views

Could the Halting Problem be “resolved” by escaping to a higher-level description of computation?

I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox. So I got to wonder: ...
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 ...
18
votes
2answers
331 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 - ...
17
votes
8answers
7k views

Why can we assume an algorithm can be represented as a bit string?

I am starting read a book about Computational Complexity and Turing Machines. Here is quote: An algorithm (i.e., a machine) can be represented as a bit string once we decide on some canonical ...
17
votes
2answers
2k views

Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?

Is a Turing machine without the ability to write on blank cells less powerful than standard Turing? I think the answer is yes but i'm unable to find a computation that standard Turing machine can do ...
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 ...
16
votes
5answers
4k views

Turing machine + time dilation = solve the halting problem?

There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer ...
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?
16
votes
3answers
693 views

Is there a TM that halts on all inputs but that property is not provable?

Does there exist a Turing machine that halts on all inputs but that property is not provable for some reason? I am wondering if this question has been studied. Note, "unprovable" could mean a "...
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. ...
16
votes
1answer
922 views

Is the unsolvability of the N-Body Problem equivalent to the Halting Problem

There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, ...
16
votes
1answer
379 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,...
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 ...
15
votes
8answers
2k views

Cardinality of the set of algorithms

Someone in a discussion brought up that (he reckons) there can be at least continuum number of strategies to approach a specific problem. The specific problem was trading strategies (not algorithms ...
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 ...
15
votes
2answers
912 views

Why is Turing completeness right?

I am using a digital computer to write this message. Such a machine has a property which, if you think about it, is actually quite remarkable: It is one machine which, if programmed appropriately, can ...
14
votes
2answers
5k views

Is it decidable whether a TM reaches some position on the tape?

I have these questions from an old exam I'm trying to solve. For each problem, the input is an encoding of some Turing machine $M$. For an integer $c>1$, and the following three problems: ...
14
votes
2answers
3k views

Connection between NAND gates and Turing completeness

I know that NAND gates can be used to create circuits that implement every truth table, and modern computers are built up of NAND gates. What is the theoretical link between NAND gates and Turing ...
13
votes
9answers
7k views

Why does a Turing machine recognise exactly one language?

I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?
13
votes
3answers
5k views

Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
13
votes
3answers
1k views

undecidable problem and its negation is undecidable

A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement. However, ...
13
votes
3answers
3k 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 ...
12
votes
3answers
3k views

Why is the blank symbol not considered part of the input alphabet of a Turing machine?

Definitions of Turing machines are always explicit about the blank symbol not being part of the input alphabet. I wonder what goes wrong when you would make it part of the input alphabet, because ...
12
votes
5answers
919 views

Goldbach Conjecture and Busy Beaver numbers?

Background: I am a complete layman in computer science. I was reading about Busy Beaver numbers here, and I found the following passage: Humanity may never know the value of BB(6) for certain, let ...
12
votes
3answers
15k 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?
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 ...