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 ...
- 81.4k
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 ...
- 3,469
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 ...
- 81.4k
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 ...
- 30k
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 ...
- 275k
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 ...
- 29.7k
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.♦
- 156k
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 ...
D.W.♦
- 156k
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 ...
- 619
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 ...
- 72k
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
...
- 8,308
34
votes
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 ...
- 3,241
31
votes
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 ...
D.W.♦
- 156k
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 ...
- 81.4k
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 ...
- 81.4k
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 ...
- 5,359
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 ...
- 887
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 ...
- 3,256
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 ...
- 72k
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 ...
- 11.9k
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 ...
- 1,845
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?
- 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 ...
- 291
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.
...
- 881
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 ...
- 478
16
votes
Accepted
What specifically makes quantum computers useful?
Destructive interference is the primary thing that makes quantum computers more powerful. In a classical probabilistic computation, having two paths to an output always makes that outcome more likely. ...
- 5,802
16
votes
Programming language where every expression makes sense
The idea of a universal Turing machine uses just such a "programming language": a coding of Turing machines as natural numbers, represented for example in binary, such that every natural number ...
- 81.4k
15
votes
Turing machine - infinite tape - does that thing exist?
The tape is not infinite. It is unbounded.
There is an important difference.
We don't need infinite memory.
We only need to be able to add more memory over time as needed.
This is actually pretty ...
- 22.2k
15
votes
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 ...
D.W.♦
- 156k
Only top scored, non community-wiki answers of a minimum length are eligible