22

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


9

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 turn every other 1 into a 0 (while skipping 0s that are already there). You keep track of the number of passes modulo 2.


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


6

Define the language $BACKPOINTER$ to have words of length $n+t\log n$, divided to $1+t$ parts, one of length $n$ and the rest of length $\log n$, by commas such that $BACKPOINTER=\{(x,p_1,\ldots,p_t)\mid x_{p_i}=1 \forall i\}$. It should follow from some standard one-way communication complexity bound that $BACKPOINTER$ needs at least $t$ bits of memory ...


6

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 language is inherently ambiguous is a separate one. The undecidability of inherent ambiguity of a CFL was proved by Ginsburg and Ullian (JACM, January 1966). https://dl.acm.org/doi/10.1145/321312.321318


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


3

Well, here are a couple of observations. There's a famous PRG by Nisan that fools $\mathsf{BPL}$-type algorithms with seed length $O(\log^2 n)$. Given two-way access to the seed, Nisan's PRG can be computed in space $O(\log n)$. Therefore, every language in $\mathsf{BPL}$ can be decided by a $\mathsf{BP}^*\mathsf{L}$-type algorithm that only uses $O(\log^2 n)...


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


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


1

Pick M to be a universal Turing machine plus two states called A and B. If you enter state A, you stay in state A forever. If you enter state B, you go through some sequence that goes through all the states, ending in A. More detailed construction is left as an exercise to the reader, but this should be fairly straightforward. Now you can diagonalize. Make ...


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