Can we have reachability properties in TLA⁺?

The source material outlines the challenge of expressing possibility and reachability properties in TLA⁺. Hillel Wayne's post highlights that TLA⁺ cannot express statements like "I can always shut down the computer" or "A user can always change their password," which require the ability to reach a state at least once, rather than always.

Lamport's book A Science of Concurrent Programs discusses this issue and introduces the ENABLED operator, which checks if an action can be taken in a given state. Using ENABLED, one can verify basic reachability properties, such as "can we reach state P within a single step?" However, this is limited to single-step reachability.

To express full reachability properties, Lamport proposes using ENABLED with a superscript plus (^+), indicating that one or more actions can be concatenated together to reach P. The notation for this is shown in the source, but TLC cannot currently check this property.

The source also mentions TLC's recent addition of support for basic reachability properties, which can be declared using the _POSSIBLE keyword. These properties are checked by TLC's breadth-first search, ensuring that P can be satisfied at least once by any behavior starting from the initial states. The source suggests that _POSSIBLE could become a more ergonomic way to express trace validation in TLC.

Finally, the article explores the concept of implementing full possibility/reachability properties in TLC, which would involve a backward reachability algorithm. This approach would require TLC to perform a breadth-first search in reverse, starting from states that satisfy P and exploring transitions back to those states. If any unexplored states remain, it indicates that P is not reachable from those states.

The source concludes by emphasizing that while this implementation is possible, it remains an untested idea.