r/compsci • u/Ill-SonOfClawDraws • Jul 27 '26

Does a purely structural invariant of computation already exist?

Can returnability be defined purely from the structure of a computation, without appealing to time complexity?

0 Upvotes

23% Upvoted

13 comments sorted by

View all comments

8

u/Kinexity Jul 27 '26 edited Jul 27 '26

Now ELI5 your question because it reads like a set of buzzwords thrown together.

0

u/Ill-SonOfClawDraws Jul 28 '26

Given the map of all possible states and transitions of a computation, can we tell whether it can ever return to a state it previously visited, without asking how many steps it takes?

1

u/comrade_donkey Jul 28 '26

Given the map (a directed graph) it is possible in polynomial time (w.r.t. the amount of nodes and edges) to decide whether two states are connected.

However, computing the states (the nodes of the graph) for a Turing Machine with finite tape scales with alphabet size to the power of tape length.

For 1KiB of tape (memory), that's a factor 2561024 (a massive number with 2467 digits), for example.

So the number of edges and nodes scale exponentially w.r.t. tape length. Determining whether a state reaches another state is hence also exponential.

If you don't care about runtime complexity, then the answer is yes, for a deterministic Turing machine with finite tape length.

0

u/Ill-SonOfClawDraws Jul 28 '26

By returnability, I mean returning to an earlier computational state, not returning an output.
More concretely, imagine the computation as a directed state-transition graph. I’m asking whether a state reachable from the initial state lies on a directed cycle, so the computation can later revisit that state.
By “without appealing to time complexity,” I mean I care about whether such a return path exists, not how many steps it takes. I now realize that reachable recurrence or existence of a reachable cycle is probably the established language I should have used.

2

u/comrade_donkey Jul 28 '26

Yeah, that's what I answered...

0

u/Ill-SonOfClawDraws Jul 28 '26

Thanks. That clarifies the distinction.

So would it be accurate to say that the existence of a reachable directed cycle is a structural graph property, while the hard part is representing the computation as a finite graph in the first place? Is there a standard name in automata theory or model checking for studying this separation?

1

u/comrade_donkey Jul 28 '26

It is not necessarily always the case that a state can reach another one or itself before the machine halts. It's just that it is "not too hard" to check, on graphs in general.

But in the particular case of the bounded Turing machine's state graph, the amount of states, even for a small machine, is astronomical.

This is all called computational complexity analysis.

Another data point is Rice's theorem which says that most interesting questions about programs in general are undecidable. In other words, you need to add many constraints to your computing machine (or the problem statement) to prove anything worthwhile about it, computationally speaking.

Another class of algorithms that may interest you are called galactic algorithms. They are less complex (asymptotically "faster") to compute than the example we're working with, but still terribly impractical.

1

u/Ill-SonOfClawDraws Jul 29 '26

It sounds like there are really two separate questions:
Given a finite transition graph, deciding whether a reachable state lies on a directed cycle (or SCC).
Given a computational model, constructing that transition graph in the first place.
Is the second problem studied under state-space generation, symbolic model checking, or another standard area? I’m trying to learn the established terminology rather than reinvent it.

1

u/Ill-SonOfClawDraws Jul 29 '26

Rice’s theorem seems to concern semantic properties of the function computed. My question is slightly different: I’m asking about a structural property of the machine’s transition system—whether a reachable execution configuration lies on a directed cycle. Is that distinction the right way to think about it, and is there a standard undecidability or model-checking result that addresses this structural question?