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 ...
20
What you want exists, and is an enormous area of research: it's the entire theory of programming languages.
Loosely speaking, you can view computation in two ways. You can think of machines, or you can think of languages.
A machine is basically some kind of finite control augmented with some (possibly unbounded) memory. This is why introductory TOC ...
13
This is not a real answer to your question (I don't know much about the (2,3) machine debate); but I suggest you the paper "Small Turing machines and generalized busy beaver competition". I quickly read it some time ago, and it has a nice graph with the borderlines between the 4 types of small TMs:
decidable
open Collatz-like problem
$3x + 1$ simulation
...
12
There have been some new results since the work cited in the previous
answers. This survey
describes the state of the art (see Figure 1). The size of the
smallest known universal Turing machine depends on the details of the
model and here are two results that are of relevance to this
discussion:
There is a 2-state, 18-symbol standard universal machine
(...
12
When I say "von Neumann architecture", I mean some hardware that is limited by the "von Neumann bottleneck" -- i.e., it has all data is funneled through some narrow data bus.
The non-von Neumann programming languages I bump into most often are VHDL and Verilog.
In VHDL and Verilog, by default, everything happens at the same time.
The programmer has to go to ...
11
I assume by non-Von Neumann, you mean languages that bypassed the "Von Neumann Bottleneck" as per Backus' paper "Can Programming Be Liberated from the Von Neumann Style?". For those interested, you can find a copy here:
http://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf
The answer to your question will have to be ambiguous for a few ...
11
It's also possible to achieve universality with 7 states and 2 symbols, although many of the same objections apply (non-uniform initial conditions on the infinite tape and unusual termination conditions). See http://11011110.livejournal.com/104656.html and http://www.complex-systems.com/abstracts/v15_i01_a01.html
These are based on simulating the Rule 110 ...
11
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
You need workspace (registers set to 0) to read the user's input. Once you've read it, and completed the program, the user needs to erase the input and the output in order to restore the workspace. However, if you assume that the user wants to keep a copy of the input and the output, this is possible to do reversibly.
Similarly for the program, to erase the ...
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, #...
8
For n-tape TMs a tight time hierarchy result similar to the space hierarchy theorem is proven by Furer in 1982. The $\lg$ factor is not needed.
The $\lg$ factor for the time hierarchy theorem stated in your post is only for single-tape TMs. Unless you are very committed to the single-tape model for some reason there is not a difference between space and ...
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
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
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 ...
answered Jan 15 '18 at 15:02
Emil Jeřábek supports Monica
11.2k3 gold badges42 silver badges65 bronze badges
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 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
Choose a universal Turing machine with $S$ states ($0\leq s < S$) and $C$ colors ($0\leq c< C$) operating on a one-dimensional tape (we'll call stuff relating to this machine "true"). Let us build together a $2$-state Turing machine (states $\text{L}$ and $\text{R}$) with $C+4SC$ colors: the true colors, and "enhanced" colors which carry info about ...
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 ...
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 ...
4
Have a look at the work of Alex Heller and Robert di Paola on dominical categories. There should be further references there to older work.
4
There is a universal simulator for $\mathsf{DSPACE}(o(\log \log n)) = \mathsf{DSPACE}(O(1))=\mathsf{REG}$. Namely, $U_{REG}(p,x)$ treats the first input $p$ as the description of a DFA, and then runs that DFA on input $x$. The universal simulator, however, is not itself in $\mathsf{DSPACE}(o(\log \log n))$---the $U_{REG}$ I just described uses space ...
4
Using a pairing function we can allow $s$ to be defined on $\mathbb{N}^2$. Let $s(i,j)=1$ if and only if the $i$'th program $P_i$ halts in at most $2^j$ steps. Then $V$ can test whether $P_i$ halts by testing $s(i,1),s(i,2),\dots$. If $U(P_i)$ halts in at most $2^j$ steps then $V(P_i)$ halts in about $(i+j)^2$ time, assuming the pairing function is sensible. ...
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
Your question states:
However, the instruction set as devised by Babbage seems to support only going back or jumping ahead one single punched card.
However, the link you supply as a reference for that says
The number starting in column 4 indicates how many cards are to be advanced past or backed up past the reader.
This would seem to render your ...
3
In the particular way you formulated the question the probability is 0. Because there are only countably many computable sequences, it suffices to show that for each computable sequence the probability is 0. So let's lets consider the sequence 000... (our reasoning works for any computable sequence).
Suppose at some time step $s = 0^n$ for some $n$. Now, ...
3
There's a comprehensive treatment of different Turing-complete computation models and proofs of their equivalence in Martin Davis, Computability and Unsolvability. Some of the most popular systems are described, including Turing-Machines, Post problems and general recursive functions.
3
Here are some references:
Claude Shannon, "A universal Turing machine with two internal states", 1956.
Marvin Minsky, "A 6-symbol 6-state Universal Turing Machine", 1960.
Shigeru Watanabe, "5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines", 1961.
Also Odifreddi writes ["Classical Recursion Theory", vol I, p. 133]:
"..., and explicit ...
3
By $T(A)$ I will mean the runtime of $A$ on the empty input, and will define $T(A) = \infty$ if $A$ doesn't halt. By $|A|$ I mean the length of $A$ in bits.
What you are trying to calculate in part (1) is:
$$T = \sum_{A | T(A) < \infty} \frac{1}{2^{|A|}}T(A)$$
Where the fraction is the Chaitin probability of generating program $A$. For each length $n$ ...
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
Yes, T>0. I am not sure I correctly get all your conditions, so I suppose that each $A_i$ is an algorithm and each of them contains an upper bound for its running time. A constant fraction of the algorithms will be the following type: "Run U on ``This'' program and if it stops in less then k steps, then output something different from its output, otherwise ...
Only top voted, non community-wiki answers of a minimum length are eligible
