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 ...
- 7,090
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, ...
- 4,400
9
votes
Smallest possible universal combinator
It should be noted that finding combinators with certain reduction properties is always difficult, and finding the smallest such combinator may easily be undecidable (for trivial reasons, as it may be ...
- 13.2k
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 ...
- 14.8k
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-...
- 743
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 ...
- 14.8k
7
votes
Smallest possible universal combinator
For your first question I believe this paper may help a bunch. It has a 6 bit combinator calculus that is also an UTM. Also it has a universal combinator that seems to have size 7 with one element ...
- 1,631
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. ...
- 560
6
votes
Accepted
What are different definitions of Universal Turing-machine?
I found some alternate definitions of Universal Turing Machine in papers related to the universality of small Turing machines and other models.
See for example the four definitions (the first 3 are ...
- 22.3k
5
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 ...
- 2,362
3
votes
Is Kolmogorov complexity a surjective function?
Just an extended comment with no deep insights: perhaps you can cheat on the encoding of a Turing machine, and build an artificial encoding that leads to a surjective Kolmogorov complexity:
$0$ ...
- 22.3k
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$. ...
- 449
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....
- 203
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, ...
- 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, ...
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 ...
- 732
1
vote
Are single hidden-layered neural networks at least as good as multi hidden-layered neural networks?
In case you're still looking for more information on this, I'll chip in my two cents.
It may help to think of neural networks as just fitting some function based on the training data. Each hidden ...
- 265
1
vote
Which models of computation can be expressed through grammars?
What about something like Peano numbers :
S -> int
int -> zero
int -> succ
zero -> "0"
succ -> "#" int
it will recognize any string ( number )...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible