I'm trying to construct a turing machine that accepts any random binary numbers. From the theory (and partial example) in this video, I understand (correctly?) that this is something that is more easily doable with a Non deterministic turing machine.

So I have come up with a concept as such that I start with state Q1 (from the left side of the band) and upon reading a zero I move right, and upon reading a One 1 move right and the machine enters the same state, again and again until the complete word is read.

I understand that this is a way I can accept an input. What I dont understand is how to include accept and reject states on the machine? I would appreciate all help on the matter.

  • 1
    $\begingroup$ What do you mean by "accepts any random binary numbers"? Please define precisely the set of numbers it should accept. Random probably isn't the right word here. $\endgroup$
    – D.W.
    Jan 18, 2020 at 17:59

1 Answer 1


There can't be "random numbers", each number is exactly that one, not at all "random". You can talk about getting a number at random from a set, perhaps according to some distribution. You might talk about a stream of bits, each of which is selected at random. But then the sequence 010101... is perfectly possible as an outcome (if it can't appear, it isn't random!).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.