|
|
|
|
|
|
5.29 Proposition (Fulk [71]) Given any scientist M, one can effectively construct scientist M' such that all the following conditions hold. |
|
|
|
|
|
|
|
|
1.  . |
|
|
|
|
|
|
|
|
2. M' is order-independent. |
|
|
|
|
|
|
|
|
3. M' is rearrangement-independent. |
|
|
|
|
|
|
|
|
4. If there exists a locking sequence for M' on L, then M' identifies L. |
|
|
|
|
|
|
|
|
5. If M' identifies L, then all texts for L contain a locking sequence for M' on L. |
|
|
|
|
|
|
|
|
5.30 Corollary (Blum and Blum [18])]  |
|
|
|
|
|
|
|
|
5.31 Coronary (Fulk [69], Schäfer-Richter [167])  |
|
|
|
|
|
|
|
|
To help prove Proposition 5.29, we introduce the following weakening of the notion of locking sequence. |
|
|
|
|
|
|
|
|
5.32 Definition (Fulk [69]) Given a scientist M and a language L, we say that s is a stabilizing sequence for M on L just in case |
|
|
|
|
|
|
|
|
(a)  , and |
|
|
|
|
|
|
|
|
(b)  . |
|
|
|
|
|
|
|
|
So, a stabilizing sequence on L is like a locking sequence on L, except that M's conjecture on it need not be an index for L. The proof of the following lemma is left to the reader. |
|
|
|
|
|
|
|
|
5.33 Lemma If M identifies L, then every stabilizing sequence for M on L is also a locking sequence for M on L. |
|
|
|
|
|
|
|
|
The next two definitions introduce some terminology we use in describing how to search for stabilizing sequences. |
|
|
|
|
|
|
|
|
5.34 Definition For each  , visible( s ) denotes the set  . |
|
|
|
|
