50 votes
Accepted

What functions can System F not compute?

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)\...
  • 13.3k
44 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

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 ...
  • 7,747
32 votes
Accepted

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

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 ...
  • 3,741
31 votes
Accepted

Turing Machine restrictions that render halting decidable

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 ...
22 votes
Accepted

Did Alan Turing's student Robin Gandy assert that Charles Babbage had no notion of a universal computing machine?

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 ...
  • 7,090
20 votes
Accepted

Source of Turing-machine illustration

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

Turing Machine restrictions that render halting decidable

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 ...
16 votes
Accepted

Looking for Literature Source for Following idea

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 ...
16 votes
Accepted

(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

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 ...
  • 26.8k
16 votes
Accepted

A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise

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 ...
  • 26.8k
15 votes

"The" category of Turing machines?

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 ...
14 votes
Accepted

Was bombe machine turing complete?

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 ...
  • 14.1k
14 votes

(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

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 ($\...
14 votes

"The" category of Turing machines?

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 ...
  • 26.8k
12 votes
Accepted

"The" category of Turing machines?

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

What functions can System F not compute?

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

Functions that are Not Efficiently Computable but Learnable

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 $...
  • 10.1k
11 votes

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

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

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Andrej Bauer gave one important reason in the comments: Because sometimes $\infty$ is a better approximation to $10000000000000000000000000000000$ than $10000000000000000000000000000000$. Let me ...
10 votes
Accepted

How good can a halting detector be?

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 ...
9 votes
Accepted

Is there a theory of computation that takes failure and decay of the computation substrate into account?

I'm not 100% sure what the question is about, but the title seems to ask about computation that allows failure. There is a lot of work on noisy (erroneous) computation in the sense that I think you ...
9 votes

Looking for Literature Source for Following idea

The idea of diagonally running all possible Turing machines has been previously used by Leonid Levin in what is now famously called Levins Universal Search. Unfortunately, and contrary to the ...
9 votes

Is Magic: the Gathering Turing complete?

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 ...
  • 191
9 votes

How is proving a context free language to be ambiguous undecidable?

The answer by apolge presents the proof that it is undecidable whether an arbitrary context free grammar is ambiguous. The question of whether a context free language is inherently ambiguous is a ...
9 votes
Accepted

Are there any open problems concerning decidability?

Given a finite automaton A over the alphabet {0,1}, does A accept the base-2 representation of at least one prime number? This is currently not known to be either decidable or undecidable. (By ...
9 votes

Understanding between lambda-calculus and other abstract machines (like Turing machine and Markov algorithm)

There are essentially two ways to describe a computational model: by describing a low level arhitectural model and its command language, that is the case of Turing Machines, Random Access Machines, ...
9 votes
Accepted

Enumerating decidable languages

You can enumerate exactly the decidable languages. I've given this question as a homework problem so I'll just give a hint here: You can modify a TM $M$ to a machine $M'$ such that if $M$ is total (...
9 votes
Accepted

$DTIME_1(o(n^2))\setminus$ REGULAR

For example, I think you can decide if $\lfloor\log_2|w|\rfloor$ is even in time $O(n\log n)$: you first overwrite the input string with all 1s, and then do $\log n$ passes over the string where you ...
8 votes

Source of Turing-machine illustration

For your alternative question: try https://commons.wikimedia.org/wiki/Category:Turing_machines (There are several images there that are similar to the one you show, and everything on Wikimedia ...
8 votes
Accepted

Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?

If the number of counters or the number of reversals (or both) is part of the input, the problem becomes coNP-complete (unless there is exactly one counter): The upper bound was shown by Hague and ...

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