2022 Developer Survey is open! Take survey.
14 votes
Accepted

Was bombe machine turing complete?

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 ...
user avatar
  • 14.1k
8 votes
Accepted

For a specific unbounded Turing machine, is its Halting problem undecidable?

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 ...
user avatar
  • 7,643
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. ...
user avatar
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 ...
user avatar
5 votes

For a specific unbounded Turing machine, is its Halting problem undecidable?

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 ...
user avatar
  • 5,712
3 votes
Accepted

Multi Head universal Turing machine

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 ...
user avatar
  • 21.3k
3 votes
Accepted

Fastest Turing Machine

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 ...
user avatar
3 votes

Fastest Turing Machine

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 ...
user avatar
  • 131
3 votes
Accepted

Is my language Turing-complete?

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 ...
user avatar
3 votes
Accepted

Turing degree of Solomonoff semi-measure

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'$.
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$. ...
user avatar
  • 449
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$ ...
user avatar
3 votes
Accepted

How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM?

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 ...
user avatar
3 votes

Can Pattern Recognition algorithms be considered Oracle Machines (in the Turing sense)?

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 ...
user avatar
  • 10k
3 votes
Accepted

Can a normal form term be extensionally equivalent to a term with no WHNF?

S(C(KM)M)I ~ MM suffices The reduction is as follows: S(C(KM)M)Ix C(KM)Mx(Ix) C(KM)Mxx KMxMx MMx
user avatar
  • 916
2 votes

Formalization of simulation for Turing machines

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 ...
user avatar
2 votes
Accepted

What is the VC dimension of Turing machines with specified maximum size?

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,...
user avatar
  • 10k
1 vote
Accepted

Where can I find a Turing machine evaluating arithmetic expressions?

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 ...
user avatar
1 vote
Accepted

About reduction relation between $HP$ and $\mathcal{E}\mbox{*}$

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

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