PRH | Essay | 7.26 • Blur, Effective Procedures, and the Church–Turing Thesis

Blur, Effective Procedures, and the Church–Turing Thesis A Blur–Epistemic Foundation for Computability Aleksandar Perišić December 2025 Abstract The Church–Turing thesis is usually presented as an empirical or philosophical claim: any “effectively calculable” function on the natural numbers is computable by a Turing machine. In this paper we argue that, once one takes seriously the epistemological role of blur—the idea that all information reaches us through finite–resolution channels, with no free infinite precision or information—the thesis stops floating in mid-air. It becomes the structural shadow of a small package of blur–native principles about descriptions, procedures, and resources. We formulate four base theories for blur–effective computation: (EffChan) discrete blur channels, (EffProc) local step rules and compositionality, (EffRes) honest resource/precision tradeoffs, and (EffSim) robustness under blur–compatible simulation. Within this framework we state a Blur–Church–Turing Schema: any model of computation that respects (EffChan)– (EffSim) computes exactly the Turing–computable partial functions on finite strings, up to blur–equivalence of outputs. Gandy’s and Boker–Dershowitz’s characterizations of computability then appear as sharp avatars of these blur–epistemic principles. We also explain why classical real–RAM or Blum–Shub–Smale machines violate the no–free–information layer and therefore inhabit a different “universe” than our blur–based one. The point is not to “prove” the Church–Turing thesis in ZFC, but to show that once blur, no–free–information, and local update are installed as basic epistemic infrastructure, the thesis is no longer an optional metaphysical add–on. It is the only way to talk about effective procedures without contradicting the way information actually reaches us. 1 Introduction The Church–Turing thesis is one of the most widely quoted, and perhaps most frequently hand–waved, principles in mathematics and theoretical computer science. In its simplest form: Any function that can be effectively calculated by a human following a fixed finite procedure can also be computed by a Turing machine. Since Turing, Church, Kleene, and others formalized a number of distinct models of computation, all of which turn out to compute the same class of partial functions N→N , the thesis has enjoyed very strong informal support; see e.g. [16,3,6,15,14]. At the same time, the thesis often feels oddly weightless. It is not a theorem of ZFC: one cannot derive it from set theory alone. It is not simply a physics statement either, because it refers to what is “effectively calculable” in principle, not to the particular particles we currently endorse. When pushed, we typically fall back on one of two types of justification: • Extensional convergence: many models (register machines, partial recursive functions, λ -calculus, Markov algorithms, . . . ) give the same class Comp of functions on N ; surely that is the “right” one. • Physics–style axioms: if a computing device is local, discrete, and bounded in the way Gandy formalizes [5], then it can be simulated by a Turing machine. 1 Both are compelling, but both leave an epistemic gap: why are we entitled to demand discreteness, locality, or the particular closure properties involved? And why should these principles extend beyond human pencil–and–paper calculations into more abstract domains (reals, functions, proofs)? The blur programme [ 8 , 9 , 10 , 11 , 7 ] takes a different starting point. Instead of beginning from machines, it begins from channels: ways in which information about a system reaches an observer. These channels always operate at finite blur; they have finite bandwidth and no free infinite precision. In this view, the basic question is not “what machine can we draw?” but “how does a learner extract more information from blur, at finite cost, in a stable way?” The aim of this paper is to recast the Church–Turing thesis in this blur–epistemic landscape. We will not attempt to compress ninety years of computability theory; instead we isolate a small package of blur–native principles that any notion of “effective procedure” must satisfy if it is to be compatible with: 1. finite blur budgets and no free infinite precision; 2. local, compositional update rules; 3. honest accounting of resources versus precision; 4. robustness under blur–compatible changes of description. Our main claim, phrased as a schema rather than a theorem, is that as soon as these principles are accepted, the Church–Turing thesis ceases to be optional. It is simply the computational face of a more primitive epistemic choice about how information behaves. Outline. Section 2 recalls the standard Church–Turing landscape and Gandy–style axioms. Section 3 summarises the blur picture and introduces blur–effective procedures. Section 4 isolates four small base theories for blur–effective computation: EffChan , EffProc , EffRes , and EffSim . In Section 5 we state the Blur–Church–Turing Schema and sketch how it reduces to existing characterizations of computability once one accepts the blur principles. Section 6 discusses examples and non–examples, including quantum and real–RAM models. Section 7 concludes with a brief outlook. 2 The classical Church–Turing landscape For orientation, we recall the standard picture; see e.g. [15,14]. 2.1 Multiple formalisms, one class By now it is classical that the following formalisms all define the same set Comp ⊆ ( NN ) partial of partial functions: •Turing machines (deterministic, on a finite alphabet) [16]; •partial recursive (or µ-recursive) functions [6]; •λ-definable functions under Church’s λ-calculus [3]; •register machines and other RAM–like models; •Markov algorithms and Post systems. The technical equivalence of these formalisms is a theorem; the thesis is the claim that this shared class Comp precisely captures informal “effective calculability” on the naturals. 2 2.2 Physical theses and Gandy machines A different line, due to Gandy [ 5 ], analyses physical mechanisms rather than human calculation. Gandy singles out a class of abstract machines (now called Gandy machines) by four principles: 1. Form of description: a machine has a set of states and a next–state function. 2. Discrete state: states are built from a finite set of basic constituents. 3. Boundedness: in any bounded region of space there is a bound on the amount of information and on the speed of information propagation. 4. Locality: the next state of a component depends only on a bounded neighbourhood. Gandy shows that any function on N computed by such a device is Turing–computable, giving a kind of physical Church–Turing thesis.1 Later work, such as [14,2], refines and generalises these axioms to arbitrary domains. 2.3 Where blur enters (but is never named) An important observation for this paper is that the classical development already hides a number of blur–like assumptions: •states carry only finite information in any bounded region (no free infinite precision); •time evolves in discrete steps or at least in locally bounded fashion; •the description of a procedure is finite and stable under coarse changes of notation. These match very well with the blur programme’s assumptions about channels, budgets, and no–free–information [ 8 , 9 , 10 ]. The difference is that, in the Church–Turing story, these principles are implicit. Our goal is to make them explicit and show that they already do much of the work of the thesis. 3 Epistemological blur and effective information We now recall, in compressed form, the blur picture developed in [8,9,10,11]. 3.1 Blur channels and budgets The starting point is that an observer never has access to a system S directly, but only through channels: Ch :S−→ (observable data). Each channel operates at a finite blur level or resolution ℓ , reflecting both noise and limited resources. One convenient abstraction is to introduce: •a partially ordered set (I, ⪯)of blur indices (coarser to finer); •for each ℓ∈Ia blur operator Bℓ:Data →Dataℓ such that Bℓ0= id at the finest scale and Bℓ2factors through Bℓ1whenever ℓ2⪰ℓ1. In practice, B ℓ is often a positive averaging: convolution with a Gaussian kernel, coarse graining of a lattice, coarse binning of measurement data, etc. Ablur budget is a lower bound ℓmin on the indices we are allowed to reach in a given investigation: we may refine ℓdown to ℓmin, but not beyond. 1 The converse—that any Turing–computable function can be realised by a Gandy machine—is also true with mild padding. 3 3.2 No free information The second key principle is that there is no free infinite precision or information in a single observable sample. The formulations in [ 9 , 10 ] are epistemic rather than physical, but the content is close to standard information–theoretic intuition. Assumption 3.1 (No free information, blur version).Fix a blur budget ℓmin . For any single realisation of a system S observed through a channel Ch and blur operators (B ℓ ) ℓ≽ℓmin , there is: • a finite description length L encoding all observable data about that realisation at blur ≥ℓmin; •a finite–capacity set of queries we can stably answer from that data alone. In particular, a single sample cannot encode arbitrarily many independent answers to arbitrary questions about Swithout violating the blur budget. In more operational terms: to learn more, one must either perform more experiments (new samples), refine the blur budget (better instruments, more time), or both. There is no hidden infinite table of answers in the first sample. 3.3 Blur–effective procedures (first pass) In this setting, an effective procedure is less about manipulating abstract infinite objects and more about reliably reducing blur around some feature of interest. Definition 3.2 (Blur–effective procedure, informal).Fix a blur budget ℓmin and a family of blur operators (Bℓ). A blur–effective procedure for a problem Pis: •a finite description π(the “program”); •a channel Ch from inputs to observable data; • a rule that, given observable data at some initial blur ℓ0 and a target blur ℓ≽ℓmin , prescribes a finite sequence of operations (querying the channel, local updates, memory manipulations) that guarantees to produce a valid answer to P at blur at least ℓ whenever one exists. The resources consumed (time, memory, number of channel queries) are allowed to depend on the target blur, but must remain finite. In most classical discrete problems, there is no explicit blur parameter; all answers are exact. In the blur picture, this corresponds to the degenerate case where answers are already stable at some coarse blur (e.g. being on one side of a finite cut). The point of keeping the blur parameter visible is that it forces us to acknowledge when an alleged “computation” is really smuggling in infinite precision for free. 4 Four base theories for blur–effective computation We now isolate four small theories that capture the blur–computational content of the informal discussion above. They are deliberately minimal: none mentions Turing machines, tapes, or states explicitly. 4 4.1 Theory EffChan: discrete blur channels Definition 4.1 (Discrete blur channels).Adiscrete blur channel structure is a tuple EffChan = (Σ,Σ∗,I,⪯,(Bℓ)ℓ∈I), where: •Σis a finite alphabet; Σ∗is the set of finite strings over Σ; •(I, ⪯)is a directed poset of blur indices with a minimum ℓ0; •for each ℓ∈Ithere is a map Bℓ: Σ∗→Σ∗such that 1. Bℓ0= idΣ∗; 2. if ℓ1⪯ℓ2then there exists a map Rℓ2,ℓ1: Σ∗→Σ∗with Bℓ2=Rℓ2,ℓ1◦Bℓ1; 3. for all w∈ Σ ∗ and ℓ we have | B ℓ ( w ) | ≤ Cℓ|w| for some constant Cℓ (no explosion of description length under blur). We interpret strings in Σ ∗ as finite descriptions, and B ℓ as admissible coarsenings of those descriptions. Remark 4.2. The restriction to a finite alphabet is not essential but reflects no–free–information: if the alphabet were uncountable (e.g. arbitrary reals), each symbol could smuggle in infinite precision. In practice one works with encodings of integers, rationals, finite graphs, etc. 4.2 Theory EffProc: local update and composition Definition 4.3 (Blur–effective step systems).Given EffChan , a blur–effective step system consists of: •a set of configurations C, each encoded by a finite string code(c)∈Σ∗; • a partial next–step map U : C⇀C such that code ( U ( c )) can be computed from code ( c ) by a finite local rule; •an initialisation map init : Σ∗→ C assigning configurations to inputs; •a set F⊆ C of halting configurations, with an output map out : F→Σ∗. We write Φ(w)≃out(Un(init(w))) if Un ( init ( w )) ∈F for some n and Uk ( init ( w )) is defined for all k≤n ; otherwise Φ( w )is undefined. The partial function Φ : Σ∗⇀Σ∗is the computed function. The key requirement here is that U is local: code ( U ( c )) is obtained from code ( c )by a finite, bounded rule. We do not yet specify the rule; that is the role of the next theory. 4.3 Theory EffRes: honest resources and precision Theory EffRes organizes the interaction between blur, step systems, and resources. Definition 4.4 (Resource measures).Aresource measure for a step system ( C, U )is a function T:C → N∪ {∞} such that: 5 •T(c)≥0for all c; •if U(c)is defined then T(U(c)) ≤T(c)+1(each step costs at least unit time); •if c∈Fis halting then T(c)is the time to reach cfrom its initial state. We allow multiple resource measures (time, space, number of channel queries), but for the conceptual discussion a single one suffices. Assumption 4.5 (Honest blur–resource tradeoff).In a blur–effective step system, the ability to reduce blur around the output at level ℓ cannot be achieved at arbitrarily low resource cost uniformly in the input. More precisely, for any nontrivial problem there is a function g : I→N such that: • to guarantee correctness of the output at blur ℓ one must in general spend at least g ( ℓ ) units of resource; •g(ℓ)→ ∞ as ℓis refined towards ℓ0(no free arbitrary precision). This assumption is a direct computational avatar of the no–free–information principle: extracting finer information costs more. 4.4 Theory EffSim: robustness under blur–compatible simulation Finally, we need a notion of when two models of computation are “the same” from the blur viewpoint. Definition 4.6 (Blur–compatible simulation).Let ( EffChan1,C1, U1 )and ( EffChan2,C2, U2 )be two blur–effective step systems, with respective blur indices I1, I2 . A blur–compatible simulation of system 1by system 2consists of: •an encoding map E: Σ∗ 1→Σ∗ 2and a decoding map D: Σ∗ 2→Σ∗ 1; •a monotone map of blur indices θ:I1→I2; •a resource overhead bound h:N→N, such that: 1. for every input w∈ Σ ∗ 1 , running U1 on w for n steps can be simulated by running U2 on E(w)for at most h(n)steps, in the sense that the blurred outputs agree: B(1) ℓΦ1(w)=B(2) θ(ℓ)D(Φ2(E(w))) whenever Φ1(w)is defined at blur ℓ; 2. conversely, any computation in system 2that remains within the image of E corresponds to a computation in system 1with comparable resources. We say the two systems are blur–equivalent if they admit mutual blur–compatible simulations. Assumption 4.7 (Robustness under blur–equivalence).Any notion of “effective procedure” should be invariant under blur–equivalence: if two models are blur–equivalent, they compute the same class of blur–effective partial functions. This is the computational analogue of the blur–equivalence principle used in [11,13,12]. 6 5 The Blur–Church–Turing Schema With these four theories in place, we can now formulate the main schema. We first focus on discrete computation on strings, then briefly discuss reals and other higher–type objects. 5.1 Discrete case: partial functions on strings Let TM denote the standard class of (deterministic) Turing machines over a fixed finite alphabet Σ. Each M∈TM computes a partial function φM: Σ∗⇀Σ∗. Definition 5.1 (Blur–effective partial functions).Let ( EffChan,C, U )be a blur–effective step system satisfying EffChan , EffProc , EffRes , and EffSim . A partial function f : Σ ∗⇀ Σ ∗ is blur– effective if f is computed by some such system, in the sense of Theorem 3.2, with blur–robustness: Bℓ(f(w)) = Bℓ(Φ(w)) for all admissible blur levels ℓ whenever Φ( w )is defined. We write Compblur for the class of all blur–effective partial functions. Main Schema 5.2 (Blur–Church–Turing Schema, discrete case).Work in a universe where: • channels and blur operators satisfy EffChan and the no–free–information principle Theorem 3.1; • effective procedures are realised by step systems satisfying EffProc and the honest blur– resource tradeoff Theorem 4.5; •effectiveness is robust under blur–equivalence as in Theorem 4.7. Then the class Compblur of blur–effective partial functions Σ ∗⇀ Σ ∗ coincides with the Turing– computable partial functions {φM : M∈TM} , up to blur–equivalence of outputs. In particular, any model of computation in this universe that claims to be “more powerful than Turing machines” must either •violate at least one of the blur–epistemic principles above, or • compute a strictly larger class of blur–unstable functions (i.e. ones that depend on information below the blur budget). Remark 5.3. We call this a schema rather than a theorem because, as stated, it quantifies over models of computation at the meta–level. However, once a particular model is axiomatised in the spirit of Gandy machines or Boker–Dershowitz–style abstract models, the reduction to Turing computability can be made precise: one shows directly that any such model is blur– equivalent to a standard Turing model. The blur principles simply tell us that these axioms are not arbitrary; they summarise how information must behave in any universe where blur and no–free–information hold. 5.2 Sketch of the reduction We briefly sketch how Theorem 5.2 interacts with existing characterisations. Step 1: From blur–effective systems to Gandy–like axioms. The combination of EffChan and EffProc enforces: •discrete state: configurations are encoded by finite strings over a finite alphabet; •local update: the next–step map Uacts by local, bounded rules on these encodings; 7 • bounded information density: by no–free–information, a bounded amount of blur–stable information fits in any finite region of the configuration. Together with a mild spatial organisation (which can always be imposed by coding), these are extremely close to Gandy’s axioms for mechanical devices [5,14]. Step 2: Apply classical simulation theorems. Gandy’s theorem, and its refinements, then show that any function computed by such a device is Turing–computable [ 5 , 14 ]. Boker and Dershowitz [ 2 ] extend this to more general domains. From the blur standpoint, the point is not the precise form of the axioms, but the fact that they are forced on us by the blur infrastructure: any attempt to escape them either introduces infinite–precision primitives or gives up locality. Step 3: Use blur–equivalence to collapse variants. Finally, EffSim and Theorem 4.7 ensure that once we have one model satisfying these constraints (e.g. Turing machines), any other blur–equivalent model computes exactly the same class of partial functions. The choice of tape versus registers versus λ -terms becomes a matter of taste; the blur–epistemic principles fix the underlying class. 5.3 Continuous objects and higher types So far we have focused on functions Σ ∗⇀ Σ ∗ . What about functions R→R or higher types? Here blur simply makes explicit what is already standard in computable analysis: one does not compute a real number x∈R directly, but rather a name for x , typically a Cauchy sequence of rationals ( qn )with known modulus of convergence. A procedure is effective if, given a blur budget (say a requested precision 2 −n ) and a name for x , it produces an approximation to f ( x ) at that blur with finite resources [17]. From the blur viewpoint, this is exactly the same pattern: •blur on inputs: Bℓcorresponds to truncating a Cauchy name at some finite precision; •blur on outputs: the target blur is the requested output precision; • no–free–information: a single real number does not come with an oracle for all its bits; we must pay to extract each additional bit; • effective procedures: Turing machines operating on names, or equivalently step systems satisfying EffChan–EffSim. In this setting, the Blur–Church–Turing Schema simply says that any blur–honest model of computation on reals (one that does not treat reals as unstructured atoms with free infinite precision) will compute exactly the functions computable in the sense of Type–2 Turing machines and computable analysis [17]. 6 Examples and non–examples We briefly survey how some familiar models sit with respect to the blur principles. 6.1 Classical discrete models Turing machines, register machines, λ -calculus. All standard discrete models over finite alphabets can be coded as step systems with: •configurations encoded as strings; •next–step maps given by finite local rules (transition functions); 8 •obvious resource measures (step count) with honest blur–resource tradeoffs; •mutual simulations with only polynomial overhead. They therefore live comfortably inside EffChan–EffSim and compute Compblur. Probabilistic and quantum computation. Probabilistic Turing machines, and quantum Turing machines with finitely many qubits and gates, also fit the blur picture at the level of computability (as opposed to complexity). The blur principles only care that: •the state space can be encoded at finite blur into strings with finite descriptions; •there is no free infinite precision in amplitudes or probabilities; •local update and honest resource tradeoffs hold. Under these constraints, the class of total functions on N computed by probabilistic or quantum machines with bounded error coincides with the Turing–computable ones; the advantage is in complexity (BPP, BQP, etc.), not in computability. 6.2 Real–RAM and Blum–Shub–Smale machines In contrast, real–RAM and Blum–Shub–Smale (BSS) models [ 1 ] treat real numbers as atomic entities that can be stored and manipulated exactly in single cells. This violates the blur–epistemic picture in two ways: •a single cell can contain infinite information (e.g. all bits of a noncomputable real); •operations may reveal arbitrarily many bits of information at unit cost. From our standpoint, such models inhabit a different universe: they explicitly postulate the existence of channels that do not obey the no–free–information principle. It is therefore not surprising that they compute more functions than Turing machines when interpreted literally. What the blur picture adds is a diagnosis: if a purported model of “physical” computation relies on BSS–style primitives, it is not simply “more powerful” than Turing; it is using a different epistemic budget. Importing such primitives into our universe would force us to rewrite the blur layer itself. 6.3 Hypercomputation proposals A similar analysis applies to hypercomputation proposals based on supertasks (performing infinitely many steps in finite time), analog devices with infinite precision, or oracle machines with access to noncomputable sets; see e.g. [ 4 ] for a survey. Each of these violates at least one of: •discrete blur channels over finite alphabets (EffChan); •honest blur–resource tradeoff (extracting infinitely many bits at finite cost); •local, finite–description update rules (EffProc). From the blur point of view, this is exactly what it means to leave our universe: one cannot keep the epistemic backdrop and simply add hypercomputation on top without paying somewhere in blur. 9