22 votes
Accepted

Did Alan Turing's student Robin Gandy assert that Charles Babbage had no notion of a universal computing machine?

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 ...
usul's user avatar
  • 7,615
12 votes
Accepted

Function that is guaranteed to be one-way if one-way functions exist?

Yes, such a function was found by Levin himself, published somewhat recently: The tale of one-way functions. Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, ...
Bjørn Kjos-Hanssen's user avatar
9 votes
Accepted

Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits

$\def\M#1{\mathrm{MOD}_{#1}}\def\F#1{\mathbb F_{#1}}$I don’t know of a reference, but here is one way how to prove the result. I’ll do it in three stages, each using one new idea: (1) multilinear ...
Emil Jeřábek's user avatar
8 votes
Accepted

theorems for universal set of quantum gates for SU(d)

I'm not aware of any proof that the Clifford group + any non-Clifford element gives a universal set of quantum gates. The closest related result that I know is that the Clifford group + any non-...
Adam Bouland's user avatar
7 votes

Justification of log f in DTIME hierarchy theorem

For a fixed number of tapes greater than one, $\mathrm{Time}(o(f)) ⊊ \mathrm{Time}(O(f)$) for time-constructible $f$. The logarithmic overhead comes from the tape reduction theorem, where any number ...
Dmytro Taranovsky's user avatar
7 votes
Accepted

Terminology about computation and Finite algebra

Such algebras are called functionally complete. Also, what you call terms are actually called polynomials. In standard terminology, term operations have a more restricted definition that allows ...
Emil Jeřábek's user avatar
7 votes

Can we not output the Kolmogorov complexity?

The question can be rephrased as whether or not $\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} = 0$, and as Denis points out in the comments this is false for some encodings. ...
Dan Brumleve's user avatar
6 votes

Smallest possible universal combinator

The smallest basis is the single point combinator A = λx λy λz. x z (y (λ_.z)) of size 4 abstractions + 3 applications, and of minimal size 26 bits in the binary lambda calculus. Minimal ...
John Tromp's user avatar
3 votes

Self-universality and Turing-completeness

Assuming we also have basic arithmetic (which presumably we do, otherwise it is not clear how to represent the syntax of the system within the system), the answer is negative. If there is a self-...
Andrej Bauer's user avatar
  • 28.7k
3 votes

Computation with cellular automata in practice

To be more precise, I would want that the runtime scaling for the universal CA of each task is the same as for the best CA specifically designed for that task. Game of life is intrinsically universal ...
user148606's user avatar
3 votes

Can we not output the Kolmogorov complexity?

I think the following works. I'll use $C(x)$ for the Kolmogorov complexity Give $U$ a time bound $t$ (say, some exponential function of the length of the input program), and call the result $U^t$. ...
Peter's user avatar
  • 459
2 votes

Is this variant of bitwise cyclic tag Turing-complete?

It is. There's a fairly simple construction compiling from CT to CT2. First, consider that it's possible to double every command in a CT program without producing any behaviour (that is, ...
ais523's user avatar
  • 121
2 votes
Accepted

Universal Boolean Formulas

A $O(2^n/\log n)$-size depth-3 universal Boolean formula was constructed in O.B. Lupanov. Complexity of the universal parallel-series network of depth 3. Trudy Matem. Inst. Steklov, 133:127-131, ...
Sasha Kozachinskiy's user avatar
2 votes
Accepted

Are single hidden-layered neural networks at least as good as multi hidden-layered neural networks?

Short answer: Not necessarily. Likely nothing fishy is going on. Longer answer: The Universal Approximation Theorem (UAT) says nothing about an individual network's capacity to approximate a function....
Christian Bueno's user avatar
1 vote

Can exponential-size depth-2 $CC^0[m]$ circuits with generalized $MOD_m$ gates compute arbitrary functions from $Z/mZ$ to $Z/2Z$?

This is not a complete answer; just partial progress. For certain output sets of the output gate (the only gate on the second layer), we can prove that there are functions uncomputable by this type of ...
Jake's user avatar
  • 1,214

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