# Tag Info

14

No, the bombe was very specific. It consisted of a bunch of enigma machines hooked together. It was very limited in its use. A more interesting question is whether the Colossus computer, also used in Bletchely Park, was Turing-complete. When asking such a question, it should be understood that no physical computer is Turing-complete, since it cannot handle ...

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

It depends in which sense you mean "undecidable". If you evaluate $M$ on the empty input, and want only to find a yes/no answer, then the algorithmic problem is trivially decidable, as answered by Gamow, since either the algorithm outputting "Yes", or the one outputting "No" is correct. you don't have to know which one is correct to prove decidability: ...

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

3

If we have a fixed number of tapes then yes we can simulate them without the logarithmic overhead. E.g simulation of two-tape (and in general $k$-tape) TMs on a two-tape machine can be done without the logarithmic factor increase. If we want to simulate an arbitrary constant number of tapes then AFAIK we don't know any such simulation. See these questions ...

3

Probably the best one can say at this level of generality is that $T_U(L,n)$ and $T_V(L,n)$ are computably related (if $U$ and $V$ are both universal), i.e. there are computable functions $f,g$ such that $T_U(L,n) \leq f(T_V(L,n))$ and $T_V(L,n) \leq g(T_U(L, n))$. The proof is exactly as you suggest, using an interpreter for one universal TM in the other ...

3

The statement $T_U(L,n) \le c_{UV} \cdot T_V(L,n)$ is not true for all choices of $U$. It's easy to think of a Universal Turing Machine that is simply inefficient. For example choose $U$ as the Machine that is equivalent to $V$ but does a useless iteration over the input tape between any two steps of $V$. This would result in a slowdown linear in $n$ ...

3

Here's a proof that the language is not Turing-complete: its Halting problem can be solved for all programs in your language. This language contains only single loops in sequence, and each loop consists of a finite number of numeric changes to the tape contents. I will gloss over the fact that BF is an 8-bit language, and grant you that the tape contents are ...

3

Note that from $m (0)$ you can compute a version of Chaitin's $\Omega$. Moreover $m (x)$ is left-c.e. uniformly in $x$. So $m$ has Turing degree $0'$.

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

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

Just an extended comment to underline how the question is (up to my knowledge) far from being solved (and easy). First of all there are no "natural" quadratic lower bounds with respect to multi-tape Turing machines (see e.g. K.W.Regan, On Superlinear Lower Bounds in Complexity Theory). So the approach, find an $O(n^2)$ problem on a 1-tape Turing ...

3

There is currently zero evidence contrary to the Church-Turing thesis -- namely that the Turing machine is the strongest physically realizable computational paradigm. In the case of AI systems, the claim is obviously wrong: these are implemented on regular computers, which are equivalent to Turing machines in computational power (or would be, if they had ...

2

First, let's clearly settle what it means for a Turing Machine to compute a function. Any specification of a deterministic TM $M$ implicitly defines, for each word $w \in \Sigma^*$, a (possibly infinite) sequence of configurations of $M$ when run on $w$ (the machine is said to halt if this sequence is finite). A configuration consists of the state of the TM, ...

2

For every concrete Turing machine $M$, the halting problem (Problem $P_M$ without input: "Does the Turing machine $M$ halt on the empty input $\varepsilon$?") is decidable. The corresponding decision algorithm is either the algorithm that outputs "Yes" and halts, or the algorithm that outputs "No" and halts.

2

The exact VC bounds will depend on the alphabet size and the exact specification of the transition function (must it always move left or right, or can it stay put, etc). For fixed alphabet size, say 2, I think you can apply the DFA-VCdim analysis of Ishigami and Tani, VC-dimensions of finite automata and commutative finite automata with $k$ letters and $n$...

1

Probably the main reason why you don't find such a machine is its complexity - most textbooks try to not overwhelm the reader with details. We can give a sketch of how to construct it, however. Note that I will make a simplifying assumption, namely that (unlike your example) the expressions are fully parenthesized. I also assume that we already have Turing ...

1

Note that any computable language $L$ can be turing-reduced to any other language $L'$ which contains at least one yes-instance and one no-instance (i.e. we have $L \leq L'$) by letting the reduction mapping do all the computation and then mapping to a yes-instance of $L'$ if the original instance is in $L$ or a no-instance of $L'$ if it is not, so naturally ...

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