Formal Sciences
Logic
Computability Theory
ElementScope CategorySub-ItemDefinitionRecursively Enumerable (r.e.) Sets & Degrees
1. Domain1.1 Scope of the DomainBoundariesThe range of phenomena the science includes and excludes.Studies semi-decidable sets and the classification of their algorithmic difficulty. Includes r.e. sets, partial computable enumerations, Turing reductions, degrees of unsolvability, complete r.e. sets, Post’s problem, and priority constructions. Excludes sets requiring full decidability, higher-type recursion frameworks, or non-effective enumerations not representable by partial computable functions.
ScaleThe spatial, temporal, or organizational level at which the science operates (e.g., quantum, cellular, social, cosmic).Operates at the level of algorithmic enumerations, Turing reducibility, degree structures, priority constructions, infinite-injury arguments, and partial function behavior over ℕ.
1.2 Ontological CommitmentsEntitiesThe kinds of things assumed to exist within the domain (particles, organisms, agents, fields, etc.).r.e. sets, partial computable functions, enumeration operators, Turing functionals, degree elements, reducibility relations, complete r.e. sets (e.g., K), priority requirements, finite/infinite injury modules, approximation stages.
PropertiesThe fundamental attributes these entities possess (mass, charge, genotype, preference, etc.).Enumerability, partiality, reducibility strength, completeness, degree equivalence, jump operator behavior, monotonicity under reductions, injury levels, limit approximations, density or sparsity of enumerations.
CategoriesThe basic ontological types used to classify domain elements (substances, processes, relations, structures).r.e. vs. co-r.e. sets, Turing degrees, many-one degrees, enumeration degrees, truth-table degrees, low/high degrees, minimal degrees, promptly simple sets, creative and productive sets, priority classes.
1.3 State-VariablesVariablesThe measurable or definable properties that describe system conditions.Stage of enumeration, current approximation to set membership, requirement satisfaction state, injury level, reducibility configuration, oracle state for relative computations, current priority module status.
ParameterizationHow variables encode and represent the system’s state.Encoded by enumeration indices, Turing functional descriptions, priority orderings, requirement hierarchies, stage-wise approximations (s_0, s_1, …), injury counters, and reducibility parameters (≤_T, ≤_m, ≤_tt).
1.4 Admissible IdealizationsSimplificationsConceptual reductions used to make the domain tractable (point masses, rational agents, perfect gases).Idealizing infinite priority constructions, abstracting injury patterns, simplifying r.e. set presentations to canonical examples, using clean reducibility definitions instead of complex functional behaviors, ignoring coding overhead in reductions.
Validity ConditionsThe limits and contexts in which idealizations hold or break down.Break down when dealing with non-r.e. sets, higher recursion hierarchies, priority constructions requiring non-effective injury handling, reducibilities beyond Turing/tt/m-reducibility, or contexts where uniform enumeration breaks down.
1.5 Domain AssumptionsStructural AssumptionsBackground ontological stances such as determinism, continuity, randomness, discreteness.r.e. sets are effectively enumerable; priority constructions behave according to well-founded requirement hierarchies; reducibility captures relative computational strength; enumeration stages approximate limit behavior; Turing degrees form an upper semi-lattice.
Implicit CommitmentsUnstated but necessary assumptions that shape the field’s conceptual structure.Assumes Church–Turing-style effective definability; assumes well-founded priority hierarchies; assumes limit approximations converge in the appropriate sense; presumes reducibility relations faithfully encode relative solvability.
1.6 Internal Coherence RequirementsConsistencyThe demand that domain concepts do not contradict one another.Reducibility definitions must not contradict each other; priority constructions must satisfy all requirements without collapsing the degree structure; enumeration procedures must preserve r.e. character; complete sets must consistently encode universal problems.
CompatibilityThe requirement that entities, variables, and assumptions fit together into a unified descriptive framework.Requires alignment between enumeration procedures, reducibility frameworks, Turing degrees, jump operator behavior, priority constructions, and structural properties of the degree hierarchy (upper semilattice structure, existence of minimal pairs, etc.).
2. Evidence Layer2.1 Observable PhenomenaObservablesThe aspects of the domain that can produce detectable signals accessible to measurement.Enumeration traces of r.e. sets, stage-by-stage limit approximations, oracle-query behavior, injury patterns in priority constructions, reducibility computations, convergence/divergence behavior, jump-operator outputs.
Detection LimitsThe boundaries of what can be resolved or sensed by current instruments or methods.Limited by undecidability of halting/membership, inability to observe infinite constructions in finite time, limits of detecting true convergence, inability to inspect non-r.e. sets, and unresolvable degree relations requiring transfinite computation.
2.2 Measurement SystemsUnitsStandardized quantifications (meters, seconds, volts, decibels, dollars, etc.) necessary for consistent comparison.Enumeration stages, injury counts, requirement-satisfaction counts, oracle-query counts, reducibility-step counts, approximation depth, rate of convergence, functional evaluation steps.
InstrumentsDevices and tools (microscopes, spectrometers, sensors, surveys, detectors) used to produce measurements.Turing machine enumerators, oracle-machine simulators, priority-construction engines, enumeration operators, reducibility analyzers, jump-operator evaluators, degree-structure visualization tools.
2.3 Operational DefinitionsDefinitionsTerms defined by specific measurement procedures, ensuring empirical clarity.r.e. sets defined via effective enumeration; reducibility defined via Turing/m/tt-reductions; completeness defined via reducibility to K; degrees defined as equivalence classes; injury defined as disruption of requirement satisfaction; limits defined via stagewise stabilization.
ProceduresThe explicit steps required to perform a measurement in a reproducible way.Running enumeration procedures, conducting priority constructions, executing reducibility computations, performing oracle-based membership tests, computing jump operator outputs, tracing requirement injuries and recoveries, measuring limit-approximation behavior.
2.4 Data AcquisitionProtocolsFormal processes for gathering data under controlled or standardized conditions.Standardized enumeration runs, canonical priority frameworks, fixed reducibility protocols, controlled oracle-evaluation sequences, structured jump computations, uniform approximation sampling.
SamplingRules determining which subset of the domain is measured and how representative it is.Choosing representative r.e. sets (simple, creative, promptly simple, complete), sampling degree configurations (minimal pairs, low/high degrees), exploring variety in injury frequencies, sampling reductions across m-, T-, and tt-reducibilities.
2.5 Data Character & FormatData TypesThe form raw evidence takes (time series, spectra, images, counts, qualitative records).Enumeration logs, approximation tables, reducibility traces, oracle-query logs, injury/satisfaction histories, degree diagrams, jump outputs, partial-function evaluation traces.
ResolutionThe granularity or precision with which data is captured.Determined by granularity of stage data, frequency of approximation checkpoints, precision of reducibility logs, fidelity of oracle simulations, and ability to track long-run behavior across infinite constructions.
2.6 Reliability & CalibrationCalibrationAdjustment procedures ensuring instruments produce accurate results.Verifying enumerator correctness, validating reducibility operations against known complete sets, confirming oracle functionality, checking jump computations, cross-checking independent reconstructions of priority constructions.
Error CharacterizationIdentification and quantification of noise, uncertainty, bias, and measurement error.Mis-enumeration, incorrect reductions, misclassified convergence, false injury detection, oracle misbehavior, priority-construction inconsistencies, encoding errors, and incorrect jump-operator evaluations.
3. Structural Layer3.1 Patterns & RegularitiesLaws / RelationsStable, repeatable patterns governing how observables behave across conditions.r.e. enumeration laws; reducibility relations forming partial orders; degree structure regularities (upper semilattice behavior); jump operator patterns (e.g., A <_T A′); priority-construction laws; Post completeness phenomena; infinite injury behavior.
InvariantsQuantities or properties that remain constant under transformations (symmetries, conservation laws).Turing-degree invariants, many-one degree invariants, equivalence-class invariants under reductions, preservation of r.e.-ness under effective enumeration, invariant behavior of complete sets, monotonicity of the jump operator.
3.2 Causal ArchitectureMechanismsUnderlying processes or structures that produce the observed regularities.Enumeration-driven inclusion mechanisms, oracle computation mechanisms, injury-and-restoration mechanisms in priority constructions, finite and infinite injury modules, diagonalization mechanisms generating incomparability, jump-operator causal escalation.
PathwaysOrganized sequences of interactions forming a causal chain or network.Priority chain: assign requirement → attempt satisfaction → injury → recovery; reducibility pathway: transform membership problem of A into B; enumeration pathway: stage-by-stage build-up of r.e. set; jump pathway: A → A′ → A″ … increasing degree height.
3.3 Theoretical VocabularyConceptsCore terms that encode the domain’s structure (force, gene, equilibrium, field).r.e. set, co-r.e. set, Turing reducibility, m-reducibility, tt-reducibility, Turing degrees, complete sets, jump operator, priority requirement, injury, limit approximation, low/high degrees, minimal pairs.
ClassificationsTaxonomies, categories, or typologies that organize entities and relations.Turing degrees, m-degrees, tt-degrees, r.e. vs. non-r.e. degrees, low degrees (A′ = 0′), high degrees (A′ = 0″), minimal and minimal-pair degrees, promptly simple sets, creative and productive sets, density classifications of r.e. degrees.
3.4 Formal RepresentationsEquationsMathematical constructs expressing laws, relations, or mechanisms.Reducibility equations (A ≤_T B, A ≡T B), jump equations (A′ = deg{T}(K^A)), limit equations for r.e. approximations (A = lim_s A_s), fixed-point/diagonalization identities, priority-requirement inequalities.
ModelsStructured representations—mathematical, computational, or conceptual—used to predict and explain phenomena.Degree structure models (upper semi-lattice diagrams), infinite-injury priority models, oracle Turing machine models, stage-by-stage limit models, reducibility graphs, jump hierarchy models, approximation trees.
3.5 Idealized StructuresSimplified ModelsPurposeful abstractions that capture essential dynamics while omitting irrelevant detail.Clean one-injury priority constructions, minimal-pair templates, simplified reducibility frameworks (pure Turing/m/tt), canonical enumerations, stripped-down oracle machines, simple limit-approximation schemas.
Limit ConditionsRegimes where specific models or approximations hold (classical vs. quantum, linear vs. nonlinear).Failure of simplified priority models under infinite injury; breakdown of reducibility clarity for non-r.e. sets; limit approximations failing to stabilize; inability of simplified models to capture degree-theoretic pathologies (e.g., Sacks density theorem).
3.6 Integrative FrameworksUnifying TheoriesHigher-order structures that connect disparate laws or mechanisms under a coherent whole.Degree theory unifying all r.e. sets under Turing reducibility; jump hierarchy unifying strength stratification; priority method as unifier of construction techniques; recursion theory connecting enumerability to definability; uniform reducibility frameworks.
Interdisciplinary LinksPoints where the theory connects to adjacent sciences or larger explanatory systems.Links to computability theory, logic (arithmetical hierarchy), complexity theory (reductions), descriptive set theory (effective pointclasses), algorithmic randomness (low/high degrees), and theoretical computer science (relative computation).
4. Method Layer4.1 Inquiry DesignExperimental DesignStructured plans for manipulating variables to test causal claims.Manipulating enumeration procedures, altering reducibility parameters (Turing/m/tt), varying priority orders, modifying injury thresholds, adjusting oracle availability, testing constructions under finite vs. infinite injury, and exploring alternative diagonalization strategies.
Observational DesignSystematic approaches for gathering non-manipulated data (surveys, field studies, natural experiments).Observing enumeration and approximation behavior without intervention; tracking convergence, reducibility traces, injury events, stabilization of approximations, and oracle computations.
4.2 Testing & ValidationHypothesis TestingProcedures for evaluating whether evidence supports or contradicts specific claims.Testing reducibility claims (A ≤_T B), checking completeness via reducibility to K, evaluating whether priority requirements are satisfied, confirming convergence of limit approximations, and testing for minimal or high/low degree properties.
ReplicationThe requirement that results be independently reproducible under similar conditions.Re-running priority constructions with identical requirement orderings, replicating oracle computations, repeating reducibility simulations, re-simulating enumerations, and validating convergence across independent implementations.
4.3 Inference & EvaluationStatistical InferenceRules for drawing conclusions from noisy or incomplete data.Analyzing distributions of injury events, estimating rate of limit stabilization, comparing reducibility step counts, measuring enumeration-density behavior, and examining variation among independent constructions.
Model ComparisonCriteria (fit, simplicity, predictive accuracy, robustness) used to evaluate competing models.Comparing Turing vs. many-one vs. truth-table reducibility; comparing finite-injury vs. infinite-injury priority models; comparing enumeration operators; evaluating oracle vs. non-oracle constructions; contrasting degree-structure predictions across models.
4.4 Error ManagementError AnalysisIdentification and quantification of random and systematic errors.Identifying mis-enumeration, incorrect reductions, miscounted injuries, false convergence signals, oracle-response errors, mistaken requirement satisfaction, and inconsistencies in approximation logs.
Bias ControlMethods for minimizing subjective, instrumental, or procedural biases.Avoiding encoding bias in reductions, controlling for arbitrary or pathological priority orders, preventing cherry-picking successful constructions, ensuring balanced sampling of r.e. sets, and limiting confirmation bias in limit analyses.
4.5 Adjudication & RevisionPeer ScrutinyCollective evaluation of claims through critique, review, and debate.Reviewing priority arguments, auditing reducibility proofs, evaluating oracle constructions, comparing independent degree computations, and scrutinizing structural claims about minimal pairs, high/low degrees, and density results.
Theory RevisionProcedures for modifying, replacing, or discarding models based on new evidence.Refining reducibility definitions, updating priority frameworks, modifying enumeration operators, adjusting degree-class definitions, repairing flawed constructions, and incorporating newly discovered degree-theoretic theorems.
4.6 Integrity ConditionsTransparencyRequirements to disclose methods, data, assumptions, and limitations.Disclosing enumeration procedures, priority hierarchies, oracle specifications, reducibility mechanisms, construction scripts, and detailed stagewise approximation logs; openly stating all assumptions.
Ethical StandardsNorms ensuring responsible conduct in experimentation, data handling, and publication.Ensuring accuracy in reducibility and injury claims, avoiding hidden assumptions, maintaining reproducibility of priority constructions, reporting failures as well as successes, and accurately representing undecidability constraints.