11

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 longstanding open problem. The reason is that there is a very efficient reduction from linear time on RAMs to SAT (in general, nondeterministic quasi linear time on RAMs ...


5

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 graduate lecture series that mostly picks up where the undergrad series left off. (Note that this series does not cover logic, and I'm not aware of any videos ...


4

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 after matching ] ] If current bit is 0, jump to after matching [ The inverse of any program can be obtained by applying the following rules: \begin{align} (a ...


3

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 cellular automaton that maps $x|_{S(n)}$ to $x|_{S(n+1)}$. The initial configuration $x|_{S(0)}$ has a special quiescent state everywhere except at the origin. If ...


2

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/playlists


2

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 you're looking for, but it might be interesting to learn about. For an example, the ambient calculus. The process calculus wikipedia page includes some others.


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