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

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

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

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

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

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

### 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 ...
• 8,308

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

I can't resist... ...
• 1,681
Accepted

### Array access is O(1) implies a fixed index size, which implies O(1) array traversal?

It's a good question. From a pragmatic perspective, we tend not to worry about it. From a theoretical perspective, see the transdichotomous model. In particular, a standard assumption is that there ...
• 159k

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

### 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 ...
• 5,519

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

### 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 ...
• 3,276

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

### 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 ...
• 1,873

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

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

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

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

### Does there exist an equivalent arithmetic circuit for each computable function?

Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit. Consider any boolean function $f:\{0,1\}^n \to \{0,1\}$. Then there exists a multivariate ...
• 159k
Accepted

### Why do pushdown automata use a stack?

If you change the stack to the queue or multiple stacks, the power of computation will be increased! (as you know, we can model a queue with two stacks). If we use a queue, it can be powerful as a ...
• 3,572

### Why is the Turing Machine a popular model of computation?

I'd like to respond to this part of the question, added in an edit: "Shouldn't the canonical model of computation obviously convey the essence of computability?" One of the remarkable things that ...
• 238
Accepted

### Is there a way to test "Turing completeness"?

I don't know about specific models. It's pretty easy to become Turing Complete, since all you need is infinite search. So I can imagine a model where searching for finite vs. infiniteness boils down ...
• 29.8k