2022 Developer Survey is open! Take survey.
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)\...
user avatar
  • 13.1k
48 votes
Accepted

A total language that only a Turing complete language can interpret

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,...
user avatar
  • 26.4k
44 votes

P and NP classes explanation through lambda-calculus

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 ...
user avatar
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 ...
user avatar
  • 7,643
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 7,022
21 votes

A total language that only a Turing complete language can interpret

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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 26.4k
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 ...
user avatar
  • 26.4k
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 ...
user avatar
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 ...
user avatar
  • 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 ($\...
user avatar
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 ...
user avatar
  • 26.4k
13 votes

P and NP classes explanation through lambda-calculus

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 ...
user avatar
  • 4,400
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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
  • 10k
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 191
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar

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