6 votes

Can the minimisation operation be seen from a programming language perspective?

Is there a similar way in which the minimisation operation can be understood? More specifically, does minimisation correspond to some kind of "loop" found in programming languages? Yes, ...
confusedcius's user avatar
3 votes

Is matching pairs sufficient?

I assume that the Turing machine $M$ is allowed to be nondeterministic. In that case we need three positions. Consider the possibility that $M$ on a certain configuration may move either left or right....
Hendrik Jan's user avatar
  • 30.6k
1 vote

I am struggling to define the space complexity of a turing machine

Yes, if you can define such a TM that can solve the problem in space $O(\log n)$ that is sufficient to show that the problem is in class $A$. You should then prove that this TM never uses more than $O(...
gnarrithas's user avatar
1 vote

How to interpret Universal Quantifier in Alternating Turing Machines?

As you know, alternating Turing machines are nondeterministic, but have both existential and universal states. In an existential state one of the possible computations should accept, in a universal ...
Hendrik Jan's user avatar
  • 30.6k
1 vote

If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

Any (Turing Machine, initial tape contents) pair may be transformed into a Turing machine where each tape position is either marked or unmarked (two states), and where the tape is initially blank. ...
supercat's user avatar
  • 1,261

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