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
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
7
votes
Are there protein-based computational models?
Membrane Computing is a model that is based on the possibility or not of movement of molecules through membranes; also on possible reactions of these molecules inside a membrane compartment. While ...
- 462
7
votes
Accepted
On the complexity of a "list" datastructure in the RAM model
It appears that all of these operations can be performed in time $O(\log n/\log\log n)$ on a RAM, by combining methods for maintaining a dynamic labeling of the list elements by integers of polynomial ...
- 50.9k
6
votes
Most general setting for fine-grained exponential-time complexity classes?
(Just now noticed this question.) There are a lot of questions in the above question. I will try to just address the last few.
Might it be the case that a RAM program can solve general CNF-SAT in ...
- 27.3k
5
votes
Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals
Ryan O'Donnell (professor at Carnegie Mellon) has a wonderful undergraduate complexity theory series that goes through the fundamentals quite well, and he's an engaging lecturer. He also has a similar ...
- 1,204
5
votes
what is a model of computation, mathematically?
I think that different mathematical models of computation capture different aspects of physical reality. Similar to models of solid state physics (say), these mathematical models may be largely ...
- 5,840
5
votes
Where does the modern canonical version of the Turing machine come from?
Your question (1) is essentially the difference between Turing machines that recognize languages and Turing machines that compute functions. This difference is essential for proving theorems about ...
- 24.3k
4
votes
Where does the modern canonical version of the Turing machine come from?
I view this question as one in the history of Turing machine theory, which indeed has had more changes than are evident from contemporary textbooks. The Turing model of 1936 was remarkably different ...
- 141
4
votes
Reversible Turing tarpits?
Does Reversible Bitfuck qualify? It manipulates a tape of 1-bit cells, and its commands are
Command
Description
>
Move right
<
Move left
+
Toggle current bit
[
If current bit is 0, jump to ...
- 652
4
votes
Accepted
Examples of quasilinear vs. essentially linear time translatable models
I will start with an overall comparison of essentially linear v quasilinear, and then give a specific example of the requested computational models.
As an equivalence relation, quasilinear time (...
- 2,537
3
votes
what is a model of computation, mathematically?
As others have pointed out, "model of computation" is an open-ended concept that can hardly be captured by a single defintion. A similar example in traditional mathematics is "space".
However, this ...
- 28.3k
3
votes
Accepted
Is the following restriction of cellular automata / tile assembly / CRN a known model?
If you partition $\mathbb{Z}^d$ into the $(d-1)$-dimensional slices $S(n) := \{ \vec v | \sum_{k=1}^d \vec v_k = n \}$, then your model is essentially a spacetime diagram of the $(d-1)$-dimensional ...
- 661
3
votes
Most general setting for fine-grained exponential-time complexity classes?
Your description looks correct. The equivalence between deterministic models (under essentially linear time translation) for algorithms using $t^{o(1)}$ space (if the input size is $t^{o(1)}$ or we ...
- 2,537
2
votes
Running an algorithm for fixed amount of time on RAM model machine
One approach is to implement an interpreter for the RAM model, and then instrument the interpreter with a counter that keeps track of the number of instructions executed. I suspect it should be ...
- 11.7k
2
votes
Are there protein-based computational models?
There are models of how to compute with arbitrary chemical reactions using molecules that drift around and randomly collide. They crop up in parallel computing models sometimes. It's probably not what ...
- 353
2
votes
Characterisation of P in terms of register machines
The classic reference for these kind of results is the survey by Peter van Emde Boas, "Machine Models and Simulations", the first chapter of Handbook of Theoretical Computer Science, Vol. A.
For ...
- 21.5k
2
votes
Reversible Turing tarpits?
Many years ago I created a language called Kayak (language spec, esolangs.org entry) that was meant to be a reversible-computing tarpit. It's slightly less primitive than Reversible Brainfuck, since ...
- 186
2
votes
Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals
Prof. Tim Roughgarden (Stanford University) Lectures on algorithms and more are also great. He is one of the best lecturers out there...
https://www.youtube.com/channel/UCcH4Ga14Y4ELFKrEYM1vXCg/...
- 1,596
1
vote
Formal differences between emulation and simulation?
In plain language, emulation means the new system performs in exactly the same way as the emulated system.
Simulation means the new system performs in roughly equivalent way as the simulated system.
e....
- 11
1
vote
Accepted
Characterisation of P in terms of register machines
I was finally able to find a reference (not necessarily the oldest one) for the efficient simulation of Turing machines by means of RAMs without indirect addressing (nor binary shift):
Takumi Kasai,...
1
vote
Which model of computation is "the best"?
On a more theoretical note: The article Ultimate theoretical models of nanocomputers argues that the reversible 3D mesh model is the optimal physical model of computation, in the sense that no other ...
- 652
Only top scored, non community-wiki answers of a minimum length are eligible