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 ...
- 8,598
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,751
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.6k
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,595
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 ...
- 3,033
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 ...
- 28.3k
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 ...
- 28.3k
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 ...
- 36.9k
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 ...
- 28.3k
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 ($\...
- 5,273
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 ...
- 32.4k
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.3k
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 ...
- 27.3k
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 ...
- 3,033
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 ...
- 32.4k
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 ...
- 6,967
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
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, ...
- 631
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 (...
- 8,616
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 ...
- 8,598
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 ...
- 16.9k
8
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 ...
- 1,761
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 ...
- 351
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 ...
- 32.4k
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 ...
- 6,967
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$ ...
- 8,598
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 ...
- 24.3k
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 ...
- 1,761
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 ...
- 71
Only top scored, non community-wiki answers of a minimum length are eligible