Skip to main content
Share Your Experience: Take the 2024 Developer Survey
144 votes

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

I agree that a Turing Machine can do "all the possible mathematical problems". Well, you shouldn't, because it's not true. For example, Turing machines cannot determine if polynomials with ...
David Richerby's user avatar
77 votes
Accepted

Why is the Turing Machine a popular model of computation?

Well, a DFA is just a Turing machine that's only allowed to move to the right and that must accept or reject as soon as it runs out of input characters. So I'm not sure one can really say that a DFA ...
David Richerby's user avatar
71 votes

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

You are not correct when you repeatedly make the statements about this or that being "just a tautology". So allow me to put your claims into a bit of historical context. First of all, you need to ...
Andrej Bauer's user avatar
  • 30.8k
63 votes
Accepted

why don't we use machines with random access memory as our basic model of computation?

Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation? The short answer is that this model is actually more ...
Caleb Stanford's user avatar
61 votes
Accepted

The first Turing machine

"Turing machines" (or "a-machines") are a mathematical concept, not actual, physical devices. Turing came up with them in order to write mathematical proofs about computers, with ...
Draconis's user avatar
  • 7,138
59 votes

Why is the Turing Machine a popular model of computation?

You are asking several different questions. Let me briefly answer them one by one. What is so important about the Turing machine model? During the infancy of computability theory, several models of ...
Yuval Filmus's user avatar
52 votes

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

You already have a representation of that function as text. Convert each character to a one-byte value using the ASCII encoding. Then the result is a sequence of bytes, i.e., a sequence of bits, i.e....
D.W.'s user avatar
  • 161k
51 votes

Theoretical machines which are more powerful than Turing machines

Yes, there are theoretical machines which exceed the Turing machines in computational power, such as Oracle machines and Infinite time Turing machines. The buzzword that you should feed to Google is ...
Andrej Bauer's user avatar
  • 30.8k
47 votes
Accepted

Church-Turing Thesis and computational power of neural networks

No, it's still consistent with the Church-Turing thesis, their model comes equipped with genuine real numbers (as in arbitrary elements of $\mathbb{R}$), which pretty much immediately extends the ...
Luke Mathieson's user avatar
45 votes
Accepted

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

The most naive and simple answer to your question is that the code provided (and compiled machine code) are in-fact represented as syntactic strings of {0,1}*. Additionally, since you are talking ...
Daniel F's user avatar
  • 619
44 votes

Proof of the undecidability of the Halting Problem

Ignore the picture for a moment; we'll get to it shortly. The program $H(a, b)$ is supposed to be a halt tester: when we give $H$ an input of a program $a$ (think of $a$ as the listing of a program) ...
Rick Decker's user avatar
  • 14.8k
40 votes
Accepted

Can one build a "mechanical" universal Turing machine?

Sure. Electricity is unrelated to the model of computation. The only thing you can't actually build is the infinite tape, for obvious reasons. In this sense, anything that can be built is essentially ...
Shaull's user avatar
  • 17.2k
39 votes

What does being Turing complete mean?

It's not tautological at all. A model of computation is Turing-complete if it can simulate all Turing machines, i.e., it is at least as powerful as Turing machines. One thing that Turing machines ...
David Richerby's user avatar
38 votes
Accepted

Does the Turing test have anything to do with Turing completeness or Turing machines?

No, there is no relationship. The connection is that they are both based on concepts/work by Alan Turing, who was an early pioneer who made many advances.
D.W.'s user avatar
  • 161k
34 votes

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

I can't resist... ...
leftaroundabout's user avatar
33 votes
Accepted

Can we ever achieve Turing completeness?

As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. No. A model of computation is Turing-complete if it can compute ...
Jörg W Mittag's user avatar
32 votes

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

In addition to the fine answer by D.W. let me point out the difference between actual and potential infinity. A Turing machine is not actually infinite because at no point of its execution do we ...
Andrej Bauer's user avatar
  • 30.8k
31 votes
Accepted

Theoretical machines which are more powerful than Turing machines

The Church–Turing thesis (in one formulation) states that everything that can be physically computable can also be computed on a Turing machine. Assuming you believe this theses, and given that ...
Yuval Filmus's user avatar
30 votes

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

Mathematicians and philosophers often assume that machines (and here, he probably means "computers") cannot surprise us. This is because they assume that once we learn some fact, we immediately ...
David Richerby's user avatar
30 votes
Accepted

I'm trying to understand why every language has an infinite number of TMs that accept it

The correct version of the claim states that every computable language is accepted by infinitely many Turing machines. Indeed, if $L$ is computable, then there is a Turing machine $T$ that accepts it. ...
Yuval Filmus's user avatar
29 votes
Accepted

Proof of the undecidability of the Halting Problem

The proof aims to find a contradiction. You have to understand what the contradiction derived is, in order to understand why $P$ is used as an input to itself. The contradiction is, informally: if we ...
aelguindy's user avatar
  • 1,807
29 votes
Accepted

How can a Turing machine compare two strings without modifying them?

Create two new types of marks: $\dot{0}, \dot 1$. Those two will act "like" $x$, but can still keep the information about the string. So when you cross-off a letter, add a "dot" to ...
nir shahar's user avatar
  • 11.6k
28 votes
Accepted

Turing machine + time dilation = solve the halting problem?

Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. ...
Discrete lizard's user avatar
  • 8,248
28 votes
Accepted

Cardinality of the set of algorithms

An algorithm is informally described as a finite sequence of written instructions for accomplishing some task. More formally, they're identified as Turing machines, though you could equally well ...
David Richerby's user avatar
25 votes

Church-Turing Thesis and computational power of neural networks

To expand a little on Luke's answer, physically building a neural net to solve any language requires producing electronic components with infinitely precise resistances and so on. This isn't possible, ...
David Richerby's user avatar
25 votes
Accepted

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

The main reason is that it allows the machine to detect the end of its input: it's (the character before) the first blank. If you allowed blanks in the input, the machine could never know whether it ...
David Richerby's user avatar
24 votes

Can one build a "mechanical" universal Turing machine?

Sure. Not only is it possible, the first design for a Turing-complete computer was purely mechanical. This was Charles Babbage's Analytical Engine. Babbage published its design in 1837, long before ...
Gilles 'SO- stop being evil''s user avatar
24 votes

How can a Turing machine compare two strings without modifying them?

One simple way is to create a copy of the entire input right after the original input, if your TM only has a single tape. To distinguish the original from the copy you can use ## as separator. So the ...
Russel's user avatar
  • 2,745
23 votes

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

That "anything that is solvable can be represented by an algorithm" is not obvious, at all. This has been the object of intense debate, since Alan Turing, reworking ideas of Alonzo Church, proposed ...
André Souza Lemos's user avatar
22 votes

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

Turing machine are accepted because they are useful as a theoretical model. They are (relatively) easy to reason about, and the theory leads to insights that are useful. Please make sure to read ...
D.W.'s user avatar
  • 161k

Only top scored, non community-wiki answers of a minimum length are eligible