Turing-complete search

A search engine retrieves; Scry also computes. The query surface carries iteration with no structural ceiling (WITH RECURSIVE, fixpoint programs), conditional branching (if, CASE, in-walk filters), and state that feeds back and grows step to step — a recursive tape that doubles each iteration reaches 4 MiB in 21 steps and 129 ms on the live engine. That is general computation running next to the data instead of after a download: Turing-complete in the language-theoretic sense, and, like any physical machine, resource-bounded in execution — unlike most, the bounds are yours. You declare the deadline and the budget, the engine enforces both mid-flight, and the meter reports exactly what the computation read. The halting problem is yours to own, so the contract makes halting a first-class control, not a hope.

POST /v1/scry/query serves WITH RECURSIVE (one anchor, UNION ALL, one step; the CTE is read in the step’s FROM/JOIN). The Collatz trajectory of 27 — 111 conditional iterations of branch-on-state arithmetic — returns from the live engine in ~50 ms. Each iteration rescans whatever the step joins, so recursive SQL is the right tool for computed sequences and small closures; for graph walks over big corpora, programs (below) read only the frontier.

curl https://api.scry.io/v1/scry/query \
  -H "Authorization: Bearer $SCRY_API_KEY" \
  -H "Content-Type: text/plain" \
  --data "WITH RECURSIVE collatz AS (SELECT toUInt64(27) AS n, 0 AS step UNION ALL SELECT if(n % 2 = 0, intDiv(n, 2), 3 * n + 1), step + 1 FROM collatz WHERE n != 1) SELECT max(step) AS steps FROM collatz LIMIT 1"

A program is a closed JSON AST of named relations evaluated semi-naively to a fixpoint: each round expands only the newly discovered ids, one metered statement per step, under your key. Twelve registered edges span four graph corpora — OpenAlex citations (references, cited_by), Twitter reply and quote graphs (twitter.replies, twitter.quotes, index-native at ~120 ms a step), Hacker News and forum thread trees — each cataloged with its measured per-step cost, and naming an unknown edge returns that catalog. In-walk filters prune before expansion, which changes what the next round reads and bills; post-hoc filtering cannot do that. A live two-hop reply walk over a 374-node thread ran 4 statements in ~1 s.

{"program": {
  "relations": {
    "seed":   {"bodies": [[{"ids": ["1928716926609445169"]}]]},
    "thread": {"bodies": [[{"rel": "seed"}],
                          [{"rel": "thread"}, {"edge": "twitter.replies"}]],
               "emit": "counts"}
  },
  "out": ["thread"], "depth": 2}}

not_in is stratified negation applied while the walk runs: excluded nodes are never expanded, never billed. emit: "counts" answers with per-depth histograms and zero row egress — when the population’s shape is the answer, nothing else crosses the wire (every out relation carries its counts regardless). rank orders a derived set by exact cosine distance to an embedding handle you mint — the composition that works at corpus scale, where intersecting a walk with a global ANN top-k comes back near-empty. Rows return with {id, parent, depth} provenance, so every node explains how the walk reached it.

Between walks, plain SQL carries the algebra: UNION ALL / DISTINCT, INTERSECT, and EXCEPT compose scans (each parenthesized branch bounded by its own LIMIT); six join kinds; bounded-state aggregates — topK(N), groupArray(N), exact quantiles, count(DISTINCT ...) — computed over every matching row; QUALIFY, ROLLUP, TOTALS, and WITH FILL shape the result at no extra charge. Answers are computed over the full population — there is no page 2.

SELECT src, n FROM (
  (SELECT 'hackernews' AS src, count() AS n FROM hackernews.items LIMIT 1)
  UNION ALL
  (SELECT 'forums' AS src, count() AS n FROM forums.posts LIMIT 1)
) LIMIT 10

Every recursive shape runs inside bounds you declare: x-scry-max-seconds is a hard deadline the engine enforces mid-flight, x-scry-budget kills a statement the moment its metered machine burden crosses your ceiling, and programs check both at every statement boundary — depth caps and per-relation row caps besides. The envelope’s truncations list names every bound that fired; an empty list means the walk truly reached its fixpoint. That is the honest form of Turing-complete search: the computation is unrestricted, the resources are yours to grant, and the meter shows what happened either way.