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,768
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 ...
- 29.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 ...
- 29.4k
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 ...
- 29.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 ...
- 37.8k
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 ($\...
- 5,598
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 ...
- 131
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.8k
12
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.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 ...
- 27.5k
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 ...
- 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 ...
- 32.8k
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 ...
- 2,271
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,741
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,923
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 ...
- 18.2k
9
votes
Inconsistent Turing machine
The source you pointed to is not worth worrying about. Not definining the notion of "inconsistent Turing machine" is the least of its problems. One can derive arbitrary conclusions by taking ...
- 29.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,985
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.8k
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 ...
- 349
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,923
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.9k
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 ...
- 2,271
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
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 ...
- 29.4k
7
votes
Class of languages recognizable by single-tape 3-state TMs
The beast is extremely powerful, for example we can build a TM $M$ that accepts every string of the form
$L_Y = \{ r\; 0^n \; 1^m\;A \mid m \leq n \}$
and rejects every string of the form
$L_N = \{...
- 23.1k
7
votes
Accepted
How come Wikipedia says that Random Turing Machines can provide uncomputable output?
It's not uncommon for Wikipedia to say dubious things. Don't trust it as a primary reference. Beware that hypercomputation is potentially a "crank-adjacent" subject, so the Wikipedia ...
- 12.3k
6
votes
Accepted
Time Hierarchies in DSPACE(O(s(n)))
This is an open problem: It is open whether $\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$ (or even $\mathrm{NSPACE}(O(n))$). We only know that $\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\...
- 2,587
6
votes
For a specific unbounded Turing machine, is its Halting problem undecidable?
For every concrete Turing machine $M$, the halting problem (Problem $P_M$ without input: "Does the Turing machine $M$ halt on the empty input $\varepsilon$?") is decidable.
The corresponding decision ...
- 5,782
Only top scored, non community-wiki answers of a minimum length are eligible