# Tag Info

135

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 integer coefficients have integer solutions (Hilbert's tenth problem). Is Turing Machine “by definition” the most powerful machine? No. We can dream up an infinite ...

82

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 clearly that it came from the notation “$\hat{x}$” used for class-abstraction by Whitehead and Russell, by first modifying “$\hat{x}$” to “$\wedge x$” to ...

72

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 natural but a Turing machine isn't. Critique of the question aside, remember that Turing was working before computers existed. As such, he wasn't trying to ...

64

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 make the concepts you use precise. What is a problem? What is an algorithm? What is a machine? You may think these are obvious, but a good part of the 1920's and ...

58

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 this is not a "future-proof" answer: things which in the past could not be done fast enough in a single core probably can be now, and we can't predict what ...

56

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 computation were suggested, in various contexts. For example, Gödel, who was trying to understand to which proof systems his incompleteness theorem applies, ...

53

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., a string over the alphabet $\{0,1\}^*$. That's one example encoding.

47

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 computations. If you can solve a problem in time $T$ on a multi-core machine with $n$ cores, then you can solve it time $\sim Tn$ (or less look at Amdahl's law) on a ...

46

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 about turing machines, the programs they run are a linear list of operations/instructions, there is no reason these cannot be represented as bits/bytes.

38

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 on the paper or moves to look at a different place, just as the machine does. TM is archaic as Peano natural number arithmetic. TM is useless for practical ...

35

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 interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition. Why is it interesting? -- See reinierpost's ...

34

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 the number of $\beta$-reduction steps $(\lambda x.M)N \rightarrow M[N/x]$. But is this a good complexity measure? To answer this question, we should clarify ...

32

I can't resist... ⡂⡀⣀⢀⣄⡀⣰⡉⡀⠀⡀⡀⣀⠀⢀⣀⢀⣄⡀⡂⢀⣀⡀⢀⢀⡀⠀⡰⣀⠀⣀⠀⡂⡀⣀⢀⣄⡰⡀⢠⠂ ⡇⡏⠀⡇⡇⠀⢸⠀⡇⢀⡇⡏⠀⡇⣏⠀⠀⡇⠀⡇⣏⠀⣹⢸⠁⢸⠀⡇⢈⠷⡁⠀⡇⡏⠀⡇⡇⠀⡇⢼⠀ ⠁⠁⠀⠁⠈⠁⠈⠀⠈⠁⠁⠁⠀⠁⠈⠉⠀⠈⠁⠁⠈⠉⠁⠈⠀⠈⠀⠱⠉⠀⠉⠀⠁⠁⠀⠁⠈⠱⠁⠘⠄ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⢤⡀⡤⠀⣀⣀⣀⠀⢤⡀⡤⠀⠀⢰⠀⠀⢹⠠⠀ ⠀⠀⠀⣠⠛⣄⠀⠒⠒⠒⠀⣠⠛⣄⠀⠉⢹⠉⠁⢸⢀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠀ ⠀⠀⠀⣄⢄⠤⢄⢴⠤⢠⠀⢠⢠⡠⢠⡠⢄⠀⢤⡀⡤⢺⡖⠐⣷⠂⠊⢉⡆ ⠀⠀⠀⡇⠸⣍⣉⠸⣀⠸⣀⢼⢸⠀⢸⠀⢸⠀⣠⠛⣄⠀⠀⠀⠀⠀⣴⣋⡀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢱⠀ ⢸⠁ ⠊ (The ...

31

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 opportunities it has to halt, the less interesting the game is. You see very few such languages in practice because we don't just want a program to run, we want it to run ...

30

(note: the full desciption is a bit complex, and has several subtleties which I prefered to ignore. The following is merely the high-level ideas for the QTM model) When defining a Quantum Turing machine (QTM), one would like to have a simple model, similar to the classical TM (that is, a finite state machine plus an infinite tape), but allow the new model ...

30

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 understand every consequence of this fact. This is often a useful assumption, but it's easy to forget that it's false. He's saying that systems with simple, finite ...

29

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 is either always accepted (in the language) or always not accepted (not in the language). So there's no mechanism by which a single Turing machine even could ...

29

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 program is now the interpreter's data. In particular, you could perfectly well have a universal Turing machine that allowed the TM it's simulating to modify its ...

26

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 different properties At this point you may ask: why does my professor present the pushdown automaton, not some other kind of automaton? What makes the pushdown ...

24

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 computer science a different model is used, the RAM machine, which is much closer to actual computers. Since both models are p-equivalent (they simulate each ...

23

Non-deterministic algorithms are very different from probabilistic algorithms. Probabilistic algorithms are ones using coin tosses, and working "most of the time". As an example, randomized variants of quicksort work in time $\Theta(n\log n)$ in expectation (and with high probability), but if you're unlucky, could take as much as $\Theta(n^2)$. ...

23

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 a definition of computable numbers that took the form of the machine you are referring to. Importantly, those were not the only people working on this kind of ...

23

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 RAMs. You were probably thinking of the whole $\Omega$/$\Theta$/$O$-business. While it's true that you can abstract away some implementation details with ...

22

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 quantum gate modifies those distributions as time progresses. This isn't very efficient (which is why people want to build actual quantum computers) but it works.

21

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 than a DFA. However, a DFA cannot grow more states to cope with a longer input, which in effect the LBTM can do (taking the state to be the entire machine ...

19

You show that either model can simulate the other, that is given a machine in model A, show that there is a machine in model B that computes the same function. Note that this simulation does not have to be computable (but usually is). Consider, for example, pushdown automata with two stacks (2-PDA). In another question, the simulations in both directions ...

19

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 their better abilities to make conclusions from the facts.

18

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 computable by a human calculating in a step-by-step mechanical manner (without any use of intuition). This point is widely misunderstood -- see [1] for an ...

17

here is a half-baked answer: I know that Ugo Dal Lago at University of Bologna has been studying quantum lambda calculus. You may want to check his publications and perhaps this one in particular: Quantum implicit computational complexity by U. Dal Lago, A. Masini, M. Zorzi. I am saying it's a half-baked answer, because I haven't had chance to read any of ...

17

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 description of an ordinary Turing machine and its input and ask if that machine halts on that input. In a single step, you get an answer, and you can use that to ...

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