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

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

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

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

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

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

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

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

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

I can't resist... ...
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 ...

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

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

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

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

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

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

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

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

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

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