Skip to main content
Share Your Experience: Take the 2024 Developer Survey
45 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 ...
Denis's user avatar
  • 8,893
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 ...
chazisop's user avatar
  • 3,796
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 ...
Marzio De Biasi's 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 ...
usul's user avatar
  • 7,615
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 ...
Thomas Klimpel's user avatar
18 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 ...
Andrej Bauer's user avatar
  • 29.1k
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 ...
Andrej Bauer's user avatar
  • 29.1k
15 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 ($\...
Damiano Mazza's user avatar
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 ...
Joshua Grochow's user avatar
15 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 ...
Andrej Bauer's user avatar
  • 29.1k
13 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 grammar defines an inherently ambiguous ...
Michael Burke's user avatar
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 ...
Neel Krishnaswami's 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 $...
Aryeh's user avatar
  • 10.6k
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 ...
Ryan Williams's 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 ...
Thomas Klimpel's user avatar
10 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 ...
DerMolly's user avatar
  • 201
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 ...
Neel Krishnaswami's user avatar
9 votes

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

A formalism is useful or not, based on what people want to use the formalism to model and understand. The Turing machine is a formalism that is useful for understanding programs. Programs are worth ...
Eric Allender's 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, ...
Andrea Asperti's user avatar
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 (...
Lance Fortnow's user avatar
9 votes
Accepted

For a specific unbounded Turing machine, is its Halting problem undecidable?

It depends in which sense you mean "undecidable". If you evaluate $M$ on the empty input, and want only to find a yes/no answer, then the algorithmic problem is trivially decidable, as answered by ...
Denis's user avatar
  • 8,893
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 ...
Emil Jeřábek's user avatar
8 votes
Accepted

Can all mathematical operations be encoded with a Turing Complete language?

But I've come away looking for proof. How do we know all this covers all computable functions? Is there an obvious branch of Mathematics for which this is not covered? Is there a shortcoming in Lambda ...
Neel Krishnaswami's user avatar
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 ...
Georg Zetzsche's user avatar
8 votes

Where does the modern canonical version of the Turing machine come from?

Is it due to Sipser? Or Penrose? Sorry, that made me laugh out loud. Penrose? Today's notion of formal language (a language is a set of words or strings) can be traced at least as far back as Frege ...
Jeffrey Shallit's user avatar
8 votes
Accepted

Is coRE closed under concatenation?

Yes coRE is closed under concatenation: Let $L_1, L_2$ be coRE, witnessed by Turing Machines $M_1,M_2$ whose domain is the complement of $L_1,L_2$ respectively. We then build a Turing Machine $M$ ...
Denis's user avatar
  • 8,893
8 votes
Accepted

A contradiction in the realm of quantum digital and analog computation

Blum-Shub-Smale machines manage to solve NP-complete problems by using an exponential number of the digits of precision. Nothing that you can do in a physics experiment uses more than thirty digits of ...
Peter Shor 's user avatar
8 votes
Accepted

Fast algorithms for time bounded Kolmogorov complexity

TL;DR: It is believed that no polynomial time algorithm exists for neither $K_t$, $K^{poly}$ nor $KT$. We have no idea about $K^{t^{\prime}}$ since it has never really been studied. No faster ...
Eric Allender's user avatar
7 votes

Maximum computational power of a C implementation

With C11's (optional) threading library, it is possible to make a Turing complete implementation given unlimited recursion depth. Creating a new thread yields a second stack; two stacks are enough ...
Jared's user avatar
  • 71
7 votes
Accepted

Is iszero of the untyped lambda calculus sound and complete?

No, iszero does not have to test whether two functions are equal. It only has to detect a difference between them, i.e., extract enough information to tell whether ...
Andrej Bauer's user avatar
  • 29.1k

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