Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### 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 ...
• 81.8k
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 ...
• 81.8k

### 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 ...
• 30.8k
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 ...
• 7,088
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 ...
• 7,138

### 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 ...
• 277k

### 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....
• 161k

### 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 ...
• 30.8k
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 ...
• 18.2k
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 ...
• 619

### 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) ...
• 14.8k
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 ...
• 17.2k

### 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 ...
• 81.8k
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.
• 161k

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

I can't resist... ...
• 1,681
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 ...
• 6,160

### 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 ...
• 30.8k
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 ...
• 277k

### 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 ...
• 81.8k
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. ...
• 277k
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 ...
• 1,807
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 ...
• 11.6k
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. ...
• 8,248
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 ...
• 81.8k

### 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, ...
• 81.8k
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 ...
• 81.8k

### 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 ...

### 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 ...
• 2,745