1

Let f(n) be a function that returns 1 iff n consecutive 1s are found in an infinite random binary string.

What is the decidability of this function?

This is not a homework question, but my peers and I did think of it while doing reduction and decidability questions :)

Deco
  • 111
  • I couldn't add the tags "decidability" or "reduction" without 1000 rep :( – Deco Nov 17 '14 at 14:05
  • Is the string given along with $n$? – 5xum Nov 17 '14 at 14:10
  • See my edit (stating it's infinite). If it's infinite, does it matter whether it's given? – Deco Nov 18 '14 at 15:40
  • The thing is there is no such thing as a "random" sequence. Sequences, in themselves, are neither random nor non-random. It is the process with which they are obtained that is random or not. What I am saying is basically that $f$ is, at the moment, not well defined, thus its decidability cannot yet be discussed – 5xum Nov 19 '14 at 00:14

0 Answers0