Informally but clearly describe nondeterministic Turing machines $-$ multitape if you like $-$ that accept the following languages. Try to take advantage of nondeterminism to avoid iteration and save time in the non - deterministic sense. That is, prefer to have your $NTM$ branch a lot, while each branch is short.
- The language of all strings of $0's$ and $1's$ that have some string of length $100$ that repeats, not necessarily consecutively. Formally, this language is the set of strings of $0's$ and $1's$ of the form $wxyxz$, where $\mid \ x \mid = 100$, and $w,y$ and $z$ are of arbitrary length.
- The language of all strings of the form $w_{1}\#w_{2}\cdot\cdot\cdot\#w_{n}$, for any $n$ , such that each $w_{i}$ is a string of $0's$ and $1's,$ and for some $j, w_{j}$ is the integer $j$ in binary.
- The language of all strings of the same form as $(b)$ but for at least two values of $j$, we have $w_{j}$ equal to $j$ in binary.
