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 ...
12
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, 2003.
9
$\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 expansion, (2) $q$th root of unity, (3) extension field and Galois invariance:
For $q=2$, the following construction works. Let $f$ be any Boolean function. ...
9
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 undecidable to prove that a certain application of the combinator even halts).
There are several simple open questions of a similar flavor, e.g. problems #4, #...
7
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 given what you want. They call it Zot.
http://arxiv.org/pdf/cs/0508056v1.pdf
I am not sure if you can say or prove that there is a minimal combinator. The paper ...
7
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. Here is a weaker statement and an attempted proof of it that doesn't depend on any details of the encoding, but I'll assume a binary language for simplicity:
...
7
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 variables and the basic operations $f_i$, but not constants from $E$. Algebras that satisfy the stronger condition that every operation is represented by this kind of ...
6
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 equivalent and are similar to yours except that there there is also an explicit decoding function) in section 2 of Yurii Rogozhin, Small universal Turing ...
5
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-Clifford element densely generates an infinite group. (This is theorem 6.5 of Nebe et al. http://arxiv.org/abs/math/0001038v2). But this falls short of proving that ...
5
I think this question is probably better suited to cs.stackexchange.com, and I hesitate to answer it. That single qubit gates are not universal was stated by Deutsch, Barenco, and Ekert in 1995. They point out that you cannot entangle un-entangled qubits with only single qubit operators. You can also prove this without any appeal to entanglement or states ...
5
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 of tapes can be converted into two tapes (or even just a single tape and a stack and with just oblivious movement).
If the number of tapes is not fixed, we do ...
3
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$ represents the Turing machine that outputs $0$ (1 state TM);
$0p$ represents the Turing machine that outputs $p+1$ (the number represented by the binary string $p$ ...
3
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$. If a program exceeds the timebound, $U^t$ enters an infinite loop.
Let $C^t(x)$ be the shortest program for $x$ on $t$. Note that $C^t$ is computable.
Let $T(x)$ ...
2
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, A becomes AA, B becomes BB, C becomes CC). The queue of bits now has every bit doubled, but the cycle of commands only does anything with every second bit, so the modified ...
2
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, 1973 (In Russian)
In this paper Lupanov uses language of parallel-series networks, which is equivalent to De Morgan formulas with unbounded fan-in AND, OR ...
2
No, it is not necessary for a set of gates universal for quantum computation to contain a two-qubit gate.
A common example of a set of gates universal for quantum computation is $\{H, R_{\pi / 4}, \operatorname{CNOT}\}$, where $H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$ is the (one-qubit) Hadamard gate, $R_{\pi / 4} = \...
2
I'm not sure about the exact connection, but this seems related to the Friedberg-Muchnik theorem (see here): there is a r.e. set whose Turing degree is less than the halting problem. This result answered an influential question of Post and led to the introduction of the "priority method" in calculability.
2
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. Moreover it says nothing about trainability or generalization.
The UAT roughly says that for any $\epsilon>0$ and any continuous real-valued function $F$ ...
1
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 circuit. Let $m = p_1^{k_1} p_2^{k_2} ... p_r^{k_r}$ for some primes $p_i$ and powers $k_i \geq 1$; then:
For any prime $p_i$ and power $1 \leq k \leq k_i$, ...
1
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 layer increases the ability of the neural network to fit more complex functions. A network without hidden layers, often called a perceptron, is only able to fit ...
1
What about something like Peano numbers :
S -> int
int -> zero
int -> succ
zero -> "0"
succ -> "#" int
it will recognize any string ( number ) of this form :
0 // zero
#0 // one
##0 // two
and it should return a nested structure, with the deepness being the number.
But it starts getting complicated when one wants to implements ...
Only top voted, non community-wiki answers of a minimum length are eligible