143 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 ...
user avatar
85 votes
Accepted

What does the "Lambda" in "Lambda calculus" stand for?

An excerpt from History of Lambda-calculus and Combinatory Logic by F. Cardone and J.R. Hindley(2006): By the way, why did Church choose the notation “$\lambda$”? In [Church, 1964, §2] he stated ...
user avatar
  • 3,419
76 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 ...
user avatar
70 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 ...
user avatar
58 votes

Is there anything that MUST be done on a multi-core CPU?

The question is: under what constraints? There are certainly problems where, if we ask the question "can we solve this problem on hardware X in the given amount of time", the answer will be no. But ...
user avatar
  • 29.1k
58 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 ...
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....
user avatar
  • 140k
48 votes
Accepted

Is there anything that MUST be done on a multi-core CPU?

If you don't care about the running time, anything you can do on a multi-core machine, you can do on a single-core machine. A multi-core machine is just a way of speeding up some kinds of ...
user avatar
  • 140k
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 ...
user avatar
  • 609
41 votes

Is there a physical analogy to the Turing Machine?

AFAIK the Turing Machine is modeled on the idea of a human with a pen and paper. The human has a certain state in the brain, looks at the paper like the machine looks at the tape, and writes something ...
user avatar
  • 2,209
39 votes

Why do pushdown automata use a stack?

There are several possible layers to your question. Why must PDAs have a stack? -- By definition! That's just how it is. But why are they defined like that? -- Somebody thought it might turn out ...
user avatar
  • 70.8k
34 votes

How is algorithm complexity modeled for functional languages?

If you assume that the $\lambda$-calculus is a good model of functional programming languages, then one may think: the $\lambda$-calculus has a seemingly simple notion of time-complexity: just count ...
user avatar
32 votes

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

I can't resist... ...
user avatar
31 votes
Accepted

Programming language where every expression makes sense

Redcode, the assembly language behind codewars, was explicitly written to have very few halting instructions, because the code often gets mangled before it finally gives out, and the more ...
user avatar
  • 3,025
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 ...
user avatar
29 votes

Why does a Turing machine recognise exactly one language?

The language recognized by a Turing machine is, by definition, the set of strings it accepts. When an input is given to the machine, it is either accepted or not. Any particular input to that machine ...
user avatar
29 votes
Accepted

Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

Yes, it's possible. You can simulate the program by using an interpreter for the language it's written in. Now, the program (the interpreter) is fixed and the thing that used to be a self-modifying ...
user avatar
28 votes

Why do pushdown automata use a stack?

OmG and Raphael have already answered your question: pushdown automata use a stack because they're defined that way if they didn't use a stack, what you'd get is a different type of automaton, with ...
user avatar
  • 4,611
24 votes
Accepted

Is there a physical analogy to the Turing Machine?

Turing machines are one of the "original" Turing-complete computation models, along with the $\lambda$ calculus and the recursively defined recursive functions. Nowadays in many areas of theoretical ...
user avatar
24 votes

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

There is an important class of primitive recursive functions. Citing Wikipedia, [P]rimitive recursive function is roughly speaking a function that can be computed by a computer program whose loops ...
user avatar
23 votes
Accepted

Why is a quantum computer not capable of solving more problems than a classical computer?

Because a quantum computer can be simulated using a classical computer: it's essentially just linear algebra. Given a probability distribution for each of the qubits, you can keep track of how each ...
user avatar
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 ...
user avatar
23 votes

How is algorithm complexity modeled for functional languages?

Algorithm complexity is designed to be independent of lower level details. No, not really. We always count elementary operations in some machine model: Steps for Turing machines. Basic operations on ...
user avatar
  • 70.8k
21 votes
Accepted

Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?

The linear bounded Turing machine is restricted to a tape whose length is a linear function of the length of the input. If the length limit were a constant, then the machine would be no more powerful ...
user avatar
  • 11k
20 votes

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

Just an example - given chess rules, anyone should immediately figure the best strategy to play chess. Of course, it doesn't work. Even people aren't equal, and computers may outperform us due to ...
user avatar
  • 1,787
20 votes

How Turing Machine Can Never Stop?

Step 3 could be phrased more properly as "If M has already stopped by the time we get to N steps, accept". Does that help to clarify?
user avatar
  • 201
19 votes

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

First, it is important to keep in mind that Turing Machines were initially devised by Turing not as a model of any type of physically realizable computer but rather as an ideal limit to what is ...
user avatar
17 votes

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

Well, you can always consider a Turing machine equipped with an oracle for the ordinary Turing machine halting problem. That is, your new machine has a special tape, onto which it can write the ...
user avatar
17 votes

Is there anything that MUST be done on a multi-core CPU?

As other answers have pointed out, a single CPU can always emulate multiple CPUs by slicing time and playing the role of each virtual CPU. This emulation will certainly calculate the correct answers. ...
user avatar
  • 832
17 votes

Why is the Turing Machine a popular model of computation?

The underlying significance is about the idea of Turing-equivalence. The exact model isn't important, as long as it is Turing-equivalent. But it's better to use a simpler model so you could prove ...
user avatar
  • 478

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