Skip to main content
Share Your Experience: Take the 2024 Developer Survey
9 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 ...
Denis's user avatar
  • 8,893
6 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 ...
Gamow's user avatar
  • 5,772
5 votes
Accepted

Equivalence of a physical computer and Turing machine

You certainly are right that if someone says "a physical computer is just a Turing machine" then they are telling a bit of a stretcher. More accurate would be something like "anything ...
Jim Hefferon's user avatar
3 votes

Self-universality and Turing-completeness

Assuming we also have basic arithmetic (which presumably we do, otherwise it is not clear how to represent the syntax of the system within the system), the answer is negative. If there is a self-...
Andrej Bauer's user avatar
  • 29.1k
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
dspyz's user avatar
  • 916
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 ...
Aryeh's user avatar
  • 10.6k
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 ...
Marzio De Biasi's 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,...
Aryeh's user avatar
  • 10.6k
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 ...
Silence of the Lemma's user avatar
1 vote

Cook's theorem and universal machine

what Papadimitriou and Yannakakis mean is something along the following lines. Consider the language L consisting of all triples <M,x,t> where M is a nondeterministic Turing machine, x is a ...
vdbuss's user avatar
  • 11
1 vote

Asymptotic time required to simulate a Turing machine M for k steps

This problem has given me a headache too so I'll post for future reference. The way I understand it the two wikipedia articles you're referencing aren't about the same problem. Problem number one is : ...
ULechine's user avatar
  • 149
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 ...
Klaus Draeger's 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 ...
Watercrystal's user avatar

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