https://w3id.org/np/RA_msK7jQ6hqL5R2ZJqDE32DGhuPi5xSiraeFpjVWK1NI
.trig | .trig.txt | .jelly | .jelly.txt | .jsonld | .jsonld.txt | .nq | .nq.txt | .xml | .xml.txt
@prefix this: <https://w3id.org/np/RA_msK7jQ6hqL5R2ZJqDE32DGhuPi5xSiraeFpjVWK1NI> .
@prefix sub: <https://w3id.org/np/RA_msK7jQ6hqL5R2ZJqDE32DGhuPi5xSiraeFpjVWK1NI/> .
@prefix np: <http://www.nanopub.org/nschema#> .
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix npx: <http://purl.org/nanopub/x/> .
@prefix dc: <http://purl.org/dc/terms/> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
sub:Head {
this: a np:Nanopublication;
np:hasAssertion sub:assertion;
np:hasProvenance sub:provenance;
np:hasPublicationInfo sub:pubinfo .
}
sub:assertion {
<https://w3id.org/delphi/resource/assessment/wolfram2002-ch12-23--claim-test> a <https://w3id.org/delphi/ontology/Assessment>;
dc:description "analysis.py enumerates all 4096 two-state two-colour machines with the NKS numbering (p. 888) and runs each on x = 0..1023 under the one-sided convention of pp. 761/1143 (binary digits of x on cells 1, 2, ... with the least significant digit at cell 1, head starting at cell 1 in state 1, halting when the head reaches cell 0, output read from the tape); non-halting is established by a left-runaway state cycle, Brent cycle detection on full configurations, or a 20000-step cutoff. The runner is vectorised over (machine, input) pairs and is checked against a scalar reference on 32 machines x 256 inputs. For every machine and every distinct (function, halting-time) pair it takes T(n) = max halting time over inputs of length n = 3..10 and classifies growth by the pre-registered exact-then-approximate fits; the 61 machines classed 'other' are rerun on x = 0..16383 (n <= 14) with cutoff 2^17 (the pre-registered 2^20 was reduced for memory and time; the longest halting time seen is 303). Supplementary, non-pre-registered analyses: a parity-aware classifier (odd and even n fitted separately, first two lengths dropped), and for exponential pairs computing partial functions a search for machines agreeing with them on every input where they halt. Book census numbers are recorded as cross-checks. Runtime about 10 minutes.";
<http://www.w3.org/2000/01/rdf-schema#comment> "Measured: 6 distinct (function, halting-time) pairs with exponential maximum halting time, of 493 pairs over 4096 machines (n = 4096, exact enumeration up to the 20000-step cutoff (224573 of 4194304 machine-input pairs hit it and are counted as non-halting)). Interpretation: The claim is a census statement under a specific computational convention (head leaves the right end), which the book's notes state precisely and which is implemented literally. 'Rate of growth' is finite-sample: classes are assigned from n = 3..10 by exact or near-exact fits, which cannot prove asymptotics but follow the book's own method of reading growth from short inputs. 'The same function' is tested on the same finite input range including the halting/non-halting pattern.";
<http://www.w3.org/2000/01/rdf-schema#label> "Claim test of wolfram2002-ch12-23: refutes, confidence 0.4";
<http://www.w3.org/2000/01/rdf-schema#seeAlso> <https://github.com/fractastical/delphisci/blob/bf2af6ee0a84e23ffa6414ad7a0a50a8c276506e/test-data/claim-tests/wolfram-nks/wolfram2002-ch12-23/result.json>;
prov:wasAttributedTo <https://w3id.org/delphi/resource/agent/delphisci-claim-tester-claude-fable-5-1>;
<https://w3id.org/delphi/ontology/admissibleDatasets> "Planned datasets: nks-2state-2colour-halting-census-generator";
<https://w3id.org/delphi/ontology/assessmentType> "claim-test/0.1.0";
<https://w3id.org/delphi/ontology/dataKind> "computational";
<https://w3id.org/delphi/ontology/disconfirmingObservation> "Pre-registered. FAIL (refutes) if some (f, t) pair with sufficient data has a growth class other than constant, linear, quadratic or exponential and this is confirmed when the machine is rerun on x up to 2^14 - 1 with cutoff 2^20 steps (e.g. a cubic or super-exponential fit is best), or if some exponential pair has no constant-time partner computing the same function. MIXED if 'other' pairs exist but on the extended inputs fit one of the four classes within tolerance, or if the cross-check numbers disagree with the book in a way that indicates a convention mismatch.";
<https://w3id.org/delphi/ontology/evidenceAgainst> "224573 (machine, input) pairs are counted as non-halting at the 20000-step cutoff without proof; the exact agreement of the never/sometimes/always counts with the book indicates that no such pair halts later within the book's own analysis, but the halting problem for these machines is not solved here.",
"Criterion (a) failed because 49 of 493 pairs are classed 'other' by the pre-registered fits, and 56 of the 61 machines involved remain 'other' when extended to inputs of length 14. None of these is cubic or super-exponential: their T(n) alternate with the parity of n (e.g. 7, 19, 15, 27, 23, 35, 31, 43, ...) or settle after a transient, and a parity-aware fit classes 45 as linear, 6 as constant and 3 as quadratic exactly, leaving two machines (2242, 2439) with quadratic growth modulated with period 4. Reallocating the 49 pairs with the parity-aware fit gives constant 162, linear 296, quadratic 28, exponential 6 against the book's 164, 295, 27, 6. The book's statement about growth rates is therefore supported in substance; the pre-registered fit tolerance (relative RMS 0.15 on n = 3..10) was too strict for bounded oscillations around a linear trend.",
"Criterion (b) failed under the pre-registered reading that 'the same function' means agreement on all of x = 0..1023 including where a machine does not halt: the three exponential pairs computing total functions (378 with 1351, 1953, 2289) have 261-269 constant-time partners each, exactly as the book says, but the three pairs computing partial functions (924 and 2142, each undefined on one input x = 0 or x = 1 and computing x with its lowest bit cleared; 3626 with 3717, undefined on x = 0 and computing the identity) have only linear-time machines computing the same partial function. If 'same function' is read on the halting domain only, each of these has 261-269 machines producing the same outputs in a single step, and the book's statement about all six exponential cases holds.",
"The extended run used a cutoff of 2^17 instead of the pre-registered 2^20 steps because the vectorised runner's memory grows with the cutoff; the longest halting time observed among the extended machines is 303, so the reduced cutoff could only matter if a machine with sub-quadratic times up to n = 10 jumped above 131072 steps between n = 11 and 14.",
"Verdict follows the pre-registered rule literally and should be read as 'refutes as operationalised'. Every census number the book reports is reproduced: 748 machines never halt, 3348 sometimes, 1683 always; 149 total functions; 230 total (function, time) pairs; 17 machines compute x+1; machines 378, 1953, 2289 are exactly the exponential-time machines computing total functions; and all eleven example formulas (5, 6n+3, 4n+3, 2n+3, 2n^2+8n+7, 2^(n+2)-3, 2n+1, 3, 2n+1, 4n-1, ~2.5n^2) are matched exactly. The only count differences are 352 vs 351 partial functions and 493 vs 492 pairs.";
<https://w3id.org/delphi/ontology/expectedObservation> "Pre-registered. Conventions from NKS pp. 761 and 1143: tape cells i = 1, 2, ... hold the binary digits of x with the least significant digit at i = 1 (x = 0 is the single digit 0), all other cells 0; head starts at i = 1 in state 1; a step applies the rule (new state, new colour, displacement d) and moves the head to i - d; the computation is complete at the first step t at which i = 0; the output f(x) is the tape read as a binary number. Machines are numbered with the NKS scheme (p. 888). Inputs x = 0..1023 (lengths n = 1..10). Non-halting is established by (i) a cycle of states that keeps moving left on blank cells once the head is left of every visited cell, (ii) exact repetition of the configuration (Brent's algorithm), or (iii) a cutoff of 20000 steps. For each machine and each distinct (f, t) pair over x = 0..1023, T(n) = max t(x) over halting x of length n. Growth class on n = 3..10, requiring halting inputs at >= 5 of these lengths (otherwise 'insufficient'): exact fit (max residual < 1e-9) tried in the order constant, linear a+bn (b>0), quadratic a+bn+cn^2 (c>0), exponential a*2^n+b (a>0); if none is exact, the lowest-complexity of linear, quadratic, exponential (a*c^n+b, c in {2,3,4}) whose relative RMS residual over n = 3..10 is <= 0.15; else 'other'. PASS (supports) if (a) no (f, t) pair with sufficient data is classed 'other', and (b) for every exponential pair the same function f (as a map on x = 0..1023 including where it is undefined) is computed by at least one machine whose pair is classed constant. The book's census numbers (748 never halt / 3348 sometimes / 1683 always; 351 functions, 149 total; 492 (f,t) pairs; 164 constant, 295 linear, 27 quadratic, 6 exponential; machines 378, 1953, 2289 exponential with total functions; the formulas for machines 3279, 1285, 3333, 261, 1447, 1953, 1969, 3517, 3246, 3374) are recorded as cross-checks of the implementation and do not decide the verdict.";
<https://w3id.org/delphi/ontology/failCriterion> "Pre-registered. FAIL (refutes) if some (f, t) pair with sufficient data has a growth class other than constant, linear, quadratic or exponential and this is confirmed when the machine is rerun on x up to 2^14 - 1 with cutoff 2^20 steps (e.g. a cubic or super-exponential fit is best), or if some exponential pair has no constant-time partner computing the same function. MIXED if 'other' pairs exist but on the extended inputs fit one of the four classes within tolerance, or if the cross-check numbers disagree with the book in a way that indicates a convention mismatch.";
<https://w3id.org/delphi/ontology/hasConfidence> "0.4"^^xsd:double;
<https://w3id.org/delphi/ontology/hasEvidence> <https://w3id.org/delphi/resource/evidence/wolfram2002-ch12-23--claim-test--dataset-1>;
<https://w3id.org/delphi/ontology/hasVerdict> "refutes";
<https://w3id.org/delphi/ontology/hypothesis> "If the claim holds, when all 4096 two-state two-colour Turing machines are run under the book's one-sided convention on every input x with up to 10 binary digits, the maximum halting time T(n) over inputs of length n is, for every machine (and every distinct function/time pair), either constant, linear, quadratic or exponential in n, and every function computed with exponential T(n) is also computed by some two-state two-colour machine with constant T(n).";
<https://w3id.org/delphi/ontology/inferenceMethod> "analysis.py enumerates all 4096 two-state two-colour machines with the NKS numbering (p. 888) and runs each on x = 0..1023 under the one-sided convention of pp. 761/1143 (binary digits of x on cells 1, 2, ... with the least significant digit at cell 1, head starting at cell 1 in state 1, halting when the head reaches cell 0, output read from the tape); non-halting is established by a left-runaway state cycle, Brent cycle detection on full configurations, or a 20000-step cutoff. The runner is vectorised over (machine, input) pairs and is checked against a scalar reference on 32 machines x 256 inputs. For every machine and every distinct (function, halting-time) pair it takes T(n) = max halting time over inputs of length n = 3..10 and classifies growth by the pre-registered exact-then-approximate fits; the 61 machines classed 'other' are rerun on x = 0..16383 (n <= 14) with cutoff 2^17 (the pre-registered 2^20 was reduced for memory and time; the longest halting time seen is 303). Supplementary, non-pre-registered analyses: a parity-aware classifier (odd and even n fitted separately, first two lengths dropped), and for exponential pairs computing partial functions a search for machines agreeing with them on every input where they halt. Book census numbers are recorded as cross-checks. Runtime about 10 minutes.";
<https://w3id.org/delphi/ontology/passCriterion> "Pre-registered. Conventions from NKS pp. 761 and 1143: tape cells i = 1, 2, ... hold the binary digits of x with the least significant digit at i = 1 (x = 0 is the single digit 0), all other cells 0; head starts at i = 1 in state 1; a step applies the rule (new state, new colour, displacement d) and moves the head to i - d; the computation is complete at the first step t at which i = 0; the output f(x) is the tape read as a binary number. Machines are numbered with the NKS scheme (p. 888). Inputs x = 0..1023 (lengths n = 1..10). Non-halting is established by (i) a cycle of states that keeps moving left on blank cells once the head is left of every visited cell, (ii) exact repetition of the configuration (Brent's algorithm), or (iii) a cutoff of 20000 steps. For each machine and each distinct (f, t) pair over x = 0..1023, T(n) = max t(x) over halting x of length n. Growth class on n = 3..10, requiring halting inputs at >= 5 of these lengths (otherwise 'insufficient'): exact fit (max residual < 1e-9) tried in the order constant, linear a+bn (b>0), quadratic a+bn+cn^2 (c>0), exponential a*2^n+b (a>0); if none is exact, the lowest-complexity of linear, quadratic, exponential (a*c^n+b, c in {2,3,4}) whose relative RMS residual over n = 3..10 is <= 0.15; else 'other'. PASS (supports) if (a) no (f, t) pair with sufficient data is classed 'other', and (b) for every exponential pair the same function f (as a map on x = 0..1023 including where it is undefined) is computed by at least one machine whose pair is classed constant. The book's census numbers (748 never halt / 3348 sometimes / 1683 always; 351 functions, 149 total; 492 (f,t) pairs; 164 constant, 295 linear, 27 quadratic, 6 exponential; machines 378, 1953, 2289 exponential with total functions; the formulas for machines 3279, 1285, 3333, 261, 1447, 1953, 1969, 3517, 3246, 3374) are recorded as cross-checks of the implementation and do not decide the verdict.";
<https://w3id.org/delphi/ontology/preregistered> "false"^^xsd:boolean .
<https://w3id.org/delphi/resource/claim/wolfram2002-ch12-23> <https://w3id.org/delphi/ontology/hasAssessment>
<https://w3id.org/delphi/resource/assessment/wolfram2002-ch12-23--claim-test> .
<https://w3id.org/delphi/resource/evidence/wolfram2002-ch12-23--claim-test--dataset-1>
a <https://w3id.org/delphi/ontology/EvidenceItem>;
dc:description "the computational objects the claim is about";
dc:license "generated by this test";
<http://www.w3.org/2000/01/rdf-schema#label> "Dataset: All 4096 two-state two-colour Turing machines (NKS numbering) run on inputs 0..1023 under the one-sided halting convention of NKS p. 761, generated by analysis.py";
prov:wasDerivedFrom <https://www.wolframscience.com/nks/p761--undecidability-and-intractability/> .
}
sub:provenance {
<https://w3id.org/delphi/resource/agent/delphisci-claim-tester-claude-fable-5-1> a
prov:SoftwareAgent;
<http://www.w3.org/2000/01/rdf-schema#label> "delphisci claim tester (claude-fable-5.1; cursor/claim-tests-wolfram-nks-9241)";
prov:actedOnBehalfOf <https://orcid.org/0009-0007-4948-9192>;
<https://w3id.org/delphi/ontology/usesModel> <https://w3id.org/delphi/resource/model/claude-fable-5-1> .
<https://w3id.org/delphi/resource/model/claude-fable-5-1> a <https://w3id.org/delphi/ontology/LanguageModel>;
dc:identifier "claude-fable-5.1" .
sub:assertion prov:wasAttributedTo <https://w3id.org/delphi/resource/agent/delphisci-claim-tester-claude-fable-5-1>;
prov:wasDerivedFrom <https://github.com/fractastical/delphisci/blob/bf2af6ee0a84e23ffa6414ad7a0a50a8c276506e/test-data/claim-tests/wolfram-nks/wolfram2002-ch12-23/result.json>;
prov:wasGeneratedBy sub:test .
sub:plan prov:hadPlan <https://github.com/fractastical/delphisci/blob/bf2af6ee0a84e23ffa6414ad7a0a50a8c276506e/test-data/claim-tests/README.md> .
sub:test a prov:Activity;
prov:qualifiedAssociation sub:plan;
prov:wasAssociatedWith <https://w3id.org/delphi/resource/agent/delphisci-claim-tester-claude-fable-5-1> .
}
sub:pubinfo {
this: dc:created "2026-11-08T16:24:31.943Z"^^xsd:dateTime;
dc:creator <https://orcid.org/0009-0007-4948-9192>;
dc:license <https://creativecommons.org/licenses/by/4.0/>;
npx:hasNanopubType <https://w3id.org/delphi/ontology/Assessment>;
npx:introduces <https://w3id.org/delphi/resource/assessment/wolfram2002-ch12-23--claim-test>;
<http://www.w3.org/2000/01/rdf-schema#label> "Claim test of wolfram2002-ch12-23: refutes, confidence 0.4";
<https://w3id.org/delphi/ontology/domain> <https://w3id.org/delphi/resource/domain/wolfram-nks-2002> .
sub:sig npx:hasAlgorithm "RSA";
npx:hasPublicKey "MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAyFHtPB6p0mCjDozxlOY9CmO3nBm7Te3jFbXyLmM+G1tGe47Da0jYIbhkl9Oo1ZjxmCa3LCwlEqK8gj6hEIcL4ahW30JXh9HycfKVk1bugkzMEV15tJdTzAU3sGMFnbNsn43xY2LFLy45tApkRm5byEiM7oRRrooIdwoQKnP4Wzq/bfAoJ9qvW+MGkelyOTd1jbSt+KfmT7xKmDfWzAHddUlWwMX2QJOLxDaffOteTop6ZRgPiNmPJKA/S62Gac9XtSYT3oDkZ6/nr5cxxNLpOyxTf5FPISiCe11xYO/unYjY+mwnOfA8yhJIyx1l0O9I0vpOpn+E5TvyHJV+oSTrvwIDAQAB";
npx:hasSignature "lEF5wiwxsMuNsz+WPCZRawku2EUh6Ivc8Fv+DytximNxEwzctaM0wkin7WuocdqMPLPn7VhUf434JTXhFymvvvDmCA4GzLObpgm4GGI4+uYmJc9vtwYWFht4LuJr8t+YydwraeMPyFQZtcyNKSir1MqbMoAH2RfG6t5tUTBran/t4MTWhFXEVU/RPm3nZdaWKATj/fJzdJpJq6+guAOyfairutobnlwSOB0GCTaxhfvT7PXqgkIY60gumqjbefVcoGnrvW3nRT7ZINlY6Mf32RPRIXxpyc58qWIecSMdWksr0E2DyiB2+XzECMmXpzhAm+eJPMJeiXWSqBoTqP5R7Q==";
npx:hasSignatureTarget this:;
npx:signedBy <https://orcid.org/0009-0007-4948-9192> .
}