# Tag Info

21

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 Babbage's recognition of the importance of branching and iteration to universal computation. In "The Confluence of Ideas in 1936" by Gandy, as printed in the ...

8

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 about magical combat. In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem, solving a problem that has been ...

5

The mortality problem is undecidable (P.K. Hooper, Th eUndecidability of the Turing Machine Immortality Problem (1966)) The uniform mortality problem undecidability follows from the following: Theorem: A Turing machine is mortal if and only if it is uniformly mortal I found the proof in: Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. ...

5

Pavlovic et al. view Turing machines over a binary alphabet as coalgebras for the functor $\lambda X. \, 2 \times \mathcal{P}_{\mathrm{fin}}(X \times 2 \times \{\lhd,\rhd\})^2$. The symbols $\lhd$ and $\rhd$ represent thereby the tape moves. Bart Jacobs has presented in "Coalgebraic walks, in quantum and Turing computation" an approach by using a monad. He ...

4

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 from the later more accepted formulations. In more detail in terms of your questions: (1),(2) The modern formulation in terms of Recogniser, and Languages ...

3

You are right in noticing that the state space of an NL machine is only polynomially large (i.e. the number of reachable states is polynomial in the length $n$ of the input). A deterministic Logspace machine could enumerate all these states, and check whether one of them is accepting. But this is not enough. To faithfully simulate the NL machine, the ...

2

The function $PP(n)$ is essentially the Kolmogorov complexity of the number $n$, and is non-computable by standard arguments, which I present below. Suppose to the contrary that $PP$ is computable. Then so is the function $f:k\mapsto n$ that maps a number $k\in\mathbb{N}$ to the least integer $n$ such that $PP(n)>k$. (Such an $n$ always exists by simple ...

2

In regards to (2), conditional super-linear lower bounds are known. A recent preprint by Afshani, Freksen, Kamma, and Larsen proves an $\Omega(n \log n)$ lower bound for the size of Boolean circuits computing integer multiplication, assuming a certain conjecture on network coding in undirected graphs. (See also this blog post and a follow-up post.) From the ...

2

I think a candidate for such a set $\mathbb{B}$, or something very much like it, could be produced by considering an infinite sequence of singleton languages: $L_1=\{w_1\},L_2=\{w_2\},\ldots$ --- where the $w_1\cdot w_2\cdot\ldots$ form an incompressible sequence. You might be able to shave off a bit here or there (this will strongly depend on the encoding --...

1

Sure. There are Turing machines that always reject or always accept... So, one of them is surely correct...

1

People don't know if NL=L or not yet. You showed that NL$\subseteq$ PSPACE, but it has nothing to do with L.

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