# Tag Info

50

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

45

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

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

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

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

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

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

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

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

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(... 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 ... 12 Saal Hardali mentioned that he wanted a category of Turing machines to do geometry (or at least homotopy theory) on. However, there are a lot of different ways to achieve similar aims. There is a very strong analogy between computability and topology. The intuition is that termination/nontermination is like the Sierpinski space, since termination is ... 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,... 11 I will formalize a variant of this question where "efficiency" is replaced by "computability". Let$C_n$be the concept class of all languages$L\subseteq\Sigma^*$recognizable by Turing machines on$n$states or fewer. In general, for$x\in\Sigma^*$and$f\in C_n$, the problem of evaluating$f(x)$is undecidable. However, suppose we have access to a (... 11 It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in$O(n^{2-e})$time by multitape TMs, a longstanding open problem. The reason is that there is a very efficient reduction from linear time on RAMs to SAT (in general, nondeterministic quasi linear time on RAMs ... 10 Andrej Bauer gave one important reason in the comments: Because sometimes$\infty$is a better approximation to$10000000000000000000000000000000$than$10000000000000000000000000000000$. Let me complete the other answers by some points, which were probably too obvious to mention: If your goal is to study real computers, then both finite automata and ... 10 This isn't a "nice" property, because whether it's true or false depends upon the encoding. See David et al's Asymptotically almost all$\lambda$-terms are strongly normalizing, which proves what it says in the title. However, this paper also shows that the opposite holds for SKI-combinators (into which lambda-terms can be compositionally embedded). In ... 9 Alex Churchill, Stella Biderman and Austin Herrick published this paper showing that Magic is Turing Complete Abstract—Magic: The Gathering is a popular and famously complicated trading card game about magical combat. In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem, solving a problem that has been ... 9 Termination of a Turing machine (on a fixed input) is a$\Sigma^0_1$sentence and all usual first-order arithmetic theories are complete for$\Sigma^0_1$sentences, i.e. all true$\Sigma^0_1$statements are provable in these theories. If you look at totality in place of halting, i.e. a TM halts on all inputs, then that is a$\Pi^0_2\$-complete sentence and ...

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