# Tag Info

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 ...

7

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 article on it might be especially at risk of containing material of uncertain reliability. When you find something in Wikipedia you don't understand, my advice is ...

4

A piece of Lego can be seen as a Polyomino: a plane geometric figure formed by joining one or more equal squares edge to edge. In Tiling the Plane with a Fixed Number of Polyominoes [2009], Nicolas Ollinger proved that 5 polyominoes are enough to simulate any set of Wang tiles (the shapes of the polyominoes are quite complex and clearly depends on the set ...

4

For a given computable $f$, the decidability of $L_f$ is independent of the encoding of Turing machines if and only $f$ is eventually injective (i.e., there exists a finite $X\subseteq\def\N{\mathbb N}\N$ such that $f\restriction(\N\smallsetminus X)$ is injective, or equivalently, $\{\def\<#1>{\langle#1\rangle}\<n,m>:n\ne m,f(n)=f(m)\}$ is finite)...

3

Claim: for any function $f:\{0,1\}^*\to\{0,1\}^*$ (not necessarily computable) and any admissible (see comments below) encoding, the language $$L_f = \{\left<M\right> \mid M \mathrm{\ accepts\ } f(\left<M\right>)\}$$ is not decidable. Proof. Suppose, for a contradiction, that $L_f$ is decidable -- say, by a TM $M_f$. Now we construct the ...

3

Just an extended comment to underline how the question is (up to my knowledge) far from being solved (and easy). First of all there are no "natural" quadratic lower bounds with respect to multi-tape Turing machines (see e.g. K.W.Regan, On Superlinear Lower Bounds in Complexity Theory). So the approach, find an $O(n^2)$ problem on a 1-tape Turing ...

2

First, let's clearly settle what it means for a Turing Machine to compute a function. Any specification of a deterministic TM $M$ implicitly defines, for each word $w \in \Sigma^*$, a (possibly infinite) sequence of configurations of $M$ when run on $w$ (the machine is said to halt if this sequence is finite). A configuration consists of the state of the TM, ...

2

This is pretty much an open problem and subject to active research. There are a few proposals available. Here are some of the latest ones: Brain computation by assemblies of neurons Christos H. Papadimitriou, Santosh S. Vempala, Daniel Mitropolsky, Michael Collins, Wolfgang Maass Proceedings of the National Academy of Sciences Jun 2020, 117 (25) 14464-14472;...

2

Here is another way to think about the question, that does not mention types or higher-order functions. As Andrej pointed out, translations or encodings do a lot of computation. Of course, this can't be avoided when comparing models but we can ask if a double translation e.g. from lambda-calculus to Turing machines and back again, is definable or computable ...

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