# Tag Info

75

Here's my favorite analogy. Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science's dogma, the Church-Turing Thesis fails to capture all of computation, because Turing machines can't toast bread. Therefore, you need my revolutionary new model, the Toaster-Enhanced Turing Machine (TETM), which allows ...

47

System $F$ is quite expressive. As proved by Girard here, the functions of type $\mathbb{N}\rightarrow\mathbb{N}$ (where $\mathbb{N}$ is defined to be $\forall X.\ X\rightarrow (X\rightarrow X)\rightarrow X$) are exactly the definable functions ($\mathbb{N}\rightarrow\mathbb{N}$) in second order Heyting Arithmetic $\mathrm{HA}_2$. Note that this is the same ...

45

This is a badly phrased question, so let's first make sense of it. I am going to do it the style of computability theory. Thus I will use numbers instead of strings: a piece of source code is a number, rather than a string of symbols. It does not really matter, you may replace $\mathbb{N}$ with $\mathtt{string}$ throughout below. Let $\langle m, n\rangle$ ...

44

To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata. Indeed, the main difference between the two models is that with finite automata, we expect to treat data that is bigger than the state space, and Turing Machine are a model for the other way around (state space >> data) by making the ...

41

Turing-machines and $\lambda$-calculus are equivalent only w.r.t. the functions $\mathbb{N} \rightarrow \mathbb{N}$ they can define. From the point of view of computational complexity they seem to behave differently. The main reason people use Turing machines and not $\lambda$-calculus to reason about complexity is that using $\lambda$-calculus naively ...

36

I think the issue is quite simple. All interactive formalisms can be simulated by Turing machines. TMs are inconvenient languages for research on interactive computation (in most cases) because the interesting issues get drowned out in the noise of encodings. Everybody working on the mathematisation of interaction knows this. Let me explain this in more ...

32

There are two approaches when considering this question: historical that pertains to how concepts were discovered and technical which explains why certain concepts were adopted and others abandoned or even forgotten. Historically, the Turing Machine is perhaps the most intuitive model of several developed trying to answer the Entscheidungsproblem. This is ...

30

A fairly natural and studied variation is the Tape-Reversal Bounded Turing machine (the number of tape-reversals are bounded); see for example: Juris Hartmanis: Tape-Reversal Bounded Turing Machine Computations. J. Comput. Syst. Sci. 2(2): 117-135 (1968) Edit: [this variation is more artificial] the halting problem is decidable for a Non-erasing Turing ...

27

In terms of number computability (i.e., computing functions from $\mathbb{N} \to \mathbb{N}$), all known models of computation are equivalent. However, it's still true that Turing machines are fairly painful for modelling properties like interactivity. The reason is a little bit subtle, and has to do with the kinds of questions that we want to ask about ...

22

No, the opposite. This quote of Gandy's is not referring to Babbage, but to some intervening proposals for universal-style computing between Babbage and Turing. Gandy says those proposals did not have Babbage's recognition of the importance of branching and iteration to universal computation. In "The Confluence of Ideas in 1936" by Gandy, as printed in the ...

21

Can such machines be built in practice? Yes. By "machine", Schmidhuber just means "computer program". Are they at least feasible in our Universe? Not in their current form -- the algorithms are too inefficient. From a ten thousand meter perspective, Jürgen Schmidhuber (and former students, like Marcus Hutter) have been investigating the idea of ...

21

The short answer is no. The long answer is that such languages are invented on a regular basis, but if they see any significant degree of use, for good semantic reasons they never remain in this mode for very long. The basic problem is that it is very difficult to build programs compositionally using state machines. The modular construction of programs ...

21

Any language which is not Turing complete can not write an interpreter for it self. This statement is incorrect. Consider the programming language in which the semantics of every string is "Ignore your input and halt immediately". This programming language is not Turing complete but every program is an interpreter for the language.

20

The figure appears to come from the paper "Games, Logic, and Computers" by Hao Wang, which appeared in Scientific American, Volume 213, Number 5, November 1965, pages 98-106. There is a copy online here: http://www.cs.virginia.edu/cs200/readings/wang.pdf In case you're wondering how I found it, I googled 'Turing machine "memory dial"'. None of my Turing ...

18

Let me provide you with an algorithm for recursively constructing an infinite state machine to decide any language $L \subseteq \{0,1\}^\ast$ that you like. Make the initial state accept if the empty string is in the language. Create two states for the strings 0 and 1, which the initial state branches to depending on whether the first symbol is 0 or 1. ...

18

Considering how parameter passing to subroutines and a huge part of memory management in mainstream computer languages is stack based, an obvious and natural variation is to restrict the unbounded memory of a Turing machine to be a stack. Such a model has nice properties, in addition to halting being decidable (well known for PDAs): The notion of a PDA ...

17

Not even no. Algorithms are not the right class of objects to be Turing-complete; asking whether an algorithm is Turing-complete is like asking whether a cat is prime. Objects that can be Turing-complete are usually called models of computation.

16

It seems that this idea is attributed to Levin (It is called optimal search). I believe this fact is well known. A similar algorithm is described in wikipedia for instance, although using the subset sum problem. In this article from scholarpedia you can find several references on the subject, including a pointer to the original algorithm and to some other ...

16

You may wish to look at cost semantics for functional languages. These are various computational complexity measures for functional languages that do not pass through any kind of Turing machine, RAM machine, etc. A good place to start looking is this Lambda the Ultimate post, which has some good further references. Section 7.4 of Bob Harper's Practical ...

15

If your students have done any functional programming, the nicest approach I know is to start with the untyped lambda calculus, and then use the bracket abstraction theorem to translate it into SKI combinators. Then, you can use the $smn$ and $utm$ theorems to show that Turing machines form a partial combinatory algebra, and so can interpret the SKI ...

15

This is not a research-level question, but since the general level of interest seems high, here is an answer. I cannot guess from your question whether you're shooting for something that will result in the usual computable numbers, or you're trying to surpass that. First we have Turing's definition of computable real number, and it is the one others have ...

14

No, the bombe was very specific. It consisted of a bunch of enigma machines hooked together. It was very limited in its use. A more interesting question is whether the Colossus computer, also used in Bletchely Park, was Turing-complete. When asking such a question, it should be understood that no physical computer is Turing-complete, since it cannot handle ...

14

At the request of Andrej and PhD, I am turning my comment into an answer, with apologies for self-advertising. I recently wrote a paper in which I look at how to prove the Cook-Levin theorem ($\mathsf{NP}$-completeness of SAT) using a functional language (a variant of the λ-calculus) instead of Turing machines. A summary: the key notion is that of affine ...

14

If your objects are Turing machines, there are several reasonable possibilities for morphisms. For example: 1) Consider Turing machines as the automata they are, and consider the usual morphisms of automata (maps between the alphabets and the states that are consistent with one another) which also either preserve the motions of the tape head(s), or exactly ...

13

You might be interested in Turing categories by Robin Cockett and Pieter Hofstra. From the point of view of category theory the question "what is the category of Turing machines" is less interesting than "what is the categorical structure which underlies computation". Thus, Robin and Pieter identify a general kind of category that is suitable for developing ...

12

From the comment: In "Deterministic Turing Machines in the Range between Real-Time and Linear-Time" I found: ... if $r \in T^{−1}(DTM)$ and $r' \in o(r)$ then $DTIME(n+r') \subset DTIME(n+r)$ ...

12

I paste part of an answer I wrote for another question: Implicit Computational Complexity aims at characterizing complexity classes by means of dedicated languages. The first results such as Bellantoni-Cook's Theorem were stated in terms of $\mu$-recursive functions, but more recent results use the vocabulary and techniques of $\lambda$-calculus. See this ...

11

(I am retiring as no longer relevant the portion of the answer that just explained why there are no undecidable instances of a problem/no polytime algorithms with uncomputable time bound) Now the question has changed to a question about TMs whose running time is provable in some logical theory. For any (powerful enough) logical theory $T$, there exists a ...

11

It cannot be computed in time $o(n\lg n)$. Let $M$ be a machine which given an input string $x$ halts with the size of $x$ written in binary on the tape. We can add a simple (zero-space linear-time) DFA to $M$ to check if the size of the input is a power of two: just check that the first bit is 1 and the rest is zero. Let's assume that $M$ runs time \$o(...

11

It is somewhat misleading to say that Haskell's typing system is "the hinley-milner type system". Haskell's types are much more powerful, including, among others, higher-kinded types. Indeed the typing system is so powerful that you can embed Turing-complete programming languages in the typing system, see here. This is not the only reason for Haskell's power,...

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