betaFeedback

WorksComputer Science

Random Clocks on Computation Paths]{Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?

Abstract

We watch a computation only at moments chosen by a random clock that can leap ahead, pause, or step back, and we count looks rather than steps. How far can such a clock reliably see with polynomially many looks, and does stepping back help? Rare long leaps reach exponential and doubly exponential time, with infinitely many levels between polynomial and exponential time. A clock that tends to fall back sees only the start of the input, and below polynomial time we find infinitely many incomparable levels. Stepping back can help decisively. For clocks whose long leaps occur only at rare positions, no forward-only clock goes beyond polynomial time, while even single steps back raise the reach to exponential time. Stepping back cannot help, however, when the clock's leaps ignore its position.

Introduction

The object, the motivation, and the question

The object. A deterministic machine running on an input xx produces a path of configurations C0x,C1x,C2x,…C^x_0, C^x_1, C^x_2, \ldots, one per step. We do not follow this path step by step. Instead, an observer looks at it only at indices chosen by a random clock. At each tick the clock may jump forward, step back, or stay where it is, and the observer sees the configuration at the clock’s current index (Figure 1). Once the machine accepts, its accepting configuration repeats forever, so the input is recognised as soon as the clock reaches or exceeds the first accepting index.

A random clock observing a computation path and crossing an accepting tail

Figure 1. A tick updates the clock index XtX_t and supplies the observation CXtxC^x_{X_t}. Crossing means Xt≥AX_t \ge A at some observed tick; persistent acceptance makes that observation sufficient.

Why skip steps? Computations are often reused rather than carried out from scratch. A program can store a computed value and look it up when it is needed again [1]. Studies of chess expertise likewise illustrate the role of learned perceptual patterns and their recall [2]. Language models provide another contrast: a prompt may elicit written intermediate steps, or an answer directly [3]. These examples motivate asking what is gained when access to a later state replaces inspection of the intervening states. The extent of a shortcut may vary; we represent this variation by a random clock, whose jump distribution may also depend on the current position. We idealise access: a shortcut lands on the true configuration. Uncertainty concerns how far one jumps, not whether the result is correct. The examples motivate the abstraction; they do not supply its configuration-access mechanism.

Why look back? A saved earlier state can be revisited, making another route forward available. In our clocks a backward step returns to an earlier index; it does not reverse the deterministic computation. It can return the observer to a position from which a long jump starts. Backtracking in a reasoning trace is an informal analogue. In the constructions of § 6, large forward jumps are available only at specified gate positions. A forward jump can overshoot the next gate, while a step back by one can recover it. Within the prescribed families, these returns give crossing rates that no permitted forward-only clock achieves. For independent proposals, deleting backward jumps never reduces reach (Theorem 6.4).

Why count looks? Classical running time charges each executed transition. To measure access along a fixed computation path, the jumpy observation model instead charges one unit per observed configuration, and nothing for producing configurations, sampling the clock, or writing indices. This separates the logical length of a computation from the number of observations needed to recognise its outcome. Within this abstraction, threshold-crossing probabilities determine the observation budget. The resulting classes describe an observation resource, without asserting an ordinary machine speedup or a physical implementation.

The question. The clock is fixed in advance, independently of the input and the machine; a position-dependent clock uses the current index, not the contents of the configuration. This restriction matters: an externally prescribed schedule Xt=2tX_t = 2^t reaches index 2p(n)2^{p(n)} after p(n)p(n) observations, placing the access resource in the schedule itself. For a fixed random clock, the probability of reaching a threshold within qq ticks determines the languages recognisable at confidence α\alpha (Theorem 2.4). We ask which jump laws and position-dependent kernels let polynomially many observations recognise which languages, and when backward access enlarges this power beyond every comparable forward-only clock in a specified family.

Background. Didehvar developed the programme of fuzzy-time computation to reconsider the role of uncertain time in computation [4, 5]. It motivates asking how access to successive configurations affects what an observer can recognise within a given budget. The present paper is a further attempt to formalise these ideas. As a first step in this formulation, we study one perspective: stochastic access to a fixed deterministic computation path and the resulting observation complexity. A random clock selects indices by moving forward, backward, or remaining in place. This perspective separates the computation’s logical length from the observations needed to reach its accepting tail. Clocks with independent proposals are held random walks with one fixed law μ\mu, called fuzzy clocks in Theorem 2.2; we also consider position-dependent kernels. For a fixed clock, “fuzzy” concerns probabilistic uncertainty in the observed time index, rather than fuzzy-set membership. Probability specifies that clock’s motion. Possibility cuts [6] express incomplete specification by selecting allowed clock parameters; Appendix § 14 studies observation budgets common to all the permitted parameters.

A gate that a forward jump misses

The doubling gates of Theorem 6.12 illustrate the accessibility question. At a gate g=2kg = 2^k, the clock moves to 2g+12g + 1, just beyond the next gate 2g2g. A return by one reaches that gate, where the next large jump is available. A forward-only clock cannot revisit the gate just passed. If its forward displacement away from gates is bounded by a fixed integer ww, accessing another gate requires travel using those bounded steps. The proof of Theorem 6.13 charges each gate’s gain to this intervening travel and bounds the reach of every forward-only member by a linear function of the tick budget. Length-one returns instead allow logarithmic crossing budgets. Squaring gates give the corresponding polynomial forward-only bound and doubly logarithmic budget (Theorem 6.18).

This comparison concerns all forward-only kernels within the prescribed gate families. The parity clock makes a weaker comparison: deletion changes its class from exponential to polynomial time, but replacing returns with forward re-entry also restores exponential time (Theorem 6.7). Independent-proposal clocks satisfy a deletion obstruction: suppressing negative proposals never decreases their reach (Theorem 6.4).

Main results

For a clock started at zero and a fixed confidence 0<α<10 < \alpha< 1, let Rα(q)R_{\alpha}(q) be the greatest index crossed by tick qq with probability at least α\alpha. Persistent acceptance gives the reachability equivalence of Theorem 2.4: a recogniser belongs to the class exactly when its accepting times are bounded by Rα(Q(∣x∣))R_{\alpha}(Q(|x|)) for some polynomial budget QQ. Sequential input access makes small radii restrictive, while large radii permit longer computations to be observed.

The two principal construction results concern the order of classes below P and the necessity of backward access within gated families. They are followed by the deletion comparison and the iid tail hierarchy. The zero-drift example below is separate from the negative-drift antichain; no ordering between them is established.

Theorem A (Below P: locality and an antichain; Theorems 4.1, 4.6 and 4.8) Negative drift with positive forward probability and all positive moments finite gives exactly the reverse-definite languages. One computable zero-drift law has a class strictly between the reverse-definite languages and P, and computable negative-drift laws give infinitely many pairwise incomparable such classes, at every pair of confidences.

For the fixed-return gated clock of § 6.3, β∈(0,1]\beta\in(0,1] is the probability of a one-step backward return at a landing index.

Theorem B (Backward moves are necessary, and may be sparse; Theorems 6.13, 6.15, 6.16 and 6.18) In a family whose only large forward moves are doublings at powers of two, every forward-only clock has class within P, whereas steps back by one, confined to a set of indices of density zero and possibly with vanishing probability, give EXP. The fixed-return gated clock has crossing budget (1+o(1))(1+β−1)log⁡2T(1 + o(1))(1 + \beta^{-1}) \log_2 T at every confidence. With squaring gates, backward indices of counting order log⁡log⁡N\log\log N give 2EXP while forward-only clocks stay within P.

For the return-enabled parity clock of § 6.2, β∈(0,1/2]\beta\in(0,1/2] is the backward-return probability at a positive even index. Write ℓα=−ln⁡(1−α)\ell_{\alpha} = -\ln(1 - \alpha) for 0<α<10 < \alpha< 1, where ln⁡\ln is the natural logarithm.

Theorem C (When backward moves help; Theorems 6.3, 6.6 and 6.11) If the forward-displacement law is stochastically nondecreasing in position, deleting backward moves never lowers the class. For a parity-dependent clock, a step back by one reopens a heavy-sampling phase: the class rises from P to EXP and the crossing budget falls from (1+o(1))T(1 + o(1))T to (1+o(1))(1+β−1)ℓαlog⁡2T(1 + o(1))(1 + \beta^{-1})\ell_{\alpha}\log_2 T, where ℓα=−ln⁡(1−α)\ell_{\alpha} = -\ln(1 - \alpha).

Theorem D (Above P: the tail determines the class; Theorems 5.1, 5.5, 5.7 and 5.8) *For independent jumps the reach Rα(q)R_\alpha(q) lies between the α\alpha-quantile of the largest of qq proposals and qq times that quantile. Consequently one fixed computable law has class exactly EXP; for each k≥1k \ge1 one fixed computable law has class exactly QPk=DTIME(2O(log⁡kn))\mathrm{QP}_k = \mathrm{DTIME}(2^{O(\log^k n)}); and one fixed computable law has class 2EXP. All these classes are independent of the confidence, and P = QP1⊊_1 \subsetneq QP2⊊⋯⊊_2 \subsetneq\cdots\subsetneq EXP ⊊\subsetneq 2EXP.

Further results. Positive drift and the nondegenerate regular zero-drift regimes give P (Theorems 3.3 and 3.6); a polynomial forward tail can overcome negative drift (Theorem 4.4). Computable iid laws collectively give REC, and one noncomputable law gives RE (Theorems 5.10 and 5.11). Common budgets over parameter sets depend on allowed-set infima (Appendix § 14). Figure 2 and Table 1 collect the regimes.

Figure 2. The landscape of observation classes. Each sparse class lies strictly between RDEF and P; the box asserts no ordering between the zero-drift class and the negative-drift antichain.

In Table 1, δa\delta_a denotes the point-mass probability law concentrated at aa, including a=0a = 0 and a=1a = 1. For an increment KK, its positive and negative parts are K+=max⁡(K,0)K^+ = \max(K, 0) and K−=max⁡(−K,0)K^- = \max(-K, 0) (Theorem 2.5). The deletion kernel DηD_\eta replaces backward moves by holds at their starting indices and keeps forward moves unchanged (Theorem 6.1).

Techniques and related work

Holding an inadmissible proposal at its starting position is a proposal-rejection rule, a standard way to construct Markov kernels [7 Section 3.2]. It differs from Lindley’s reflected update, which resets an overshoot below zero to zero [8]. The held walk dominates the reflected walk but is not monotone in its starting position (Theorem 2.9). Reflected-walk upper bounds therefore require a separate argument for the held rule.

The elementary drift regimes use the strong law, the central limit theorem, and moment bounds. Foster–Lyapunov methods [9 Chapters 11, 14 and 15] and exponential drift analysis [10] provide the standard framework for controlling negative-drift walks. Pemantle–Rosenthal [11] prove uniform moment bounds under negative drift, including a one-sided truncation version in their Corollary 3. Our proof of Theorem 4.1 gives the held-rule crossing estimate directly by truncating negative proposals in the conditional drift. It allows infinite negative mean. The subsequent identification with bounded-prefix recognition uses sequential locality, related to classical one-tape arguments [12], rather than a further stability theorem.

HypothesesClassReference
Independent jumps
Some finite positive moment⊆\subseteq PTheorem 3.1
Integrable, positive meanPTheorem 3.3
Integrable zero drift; μ≠δ0\mu\ne\delta_0; finite variance or bounded positive jumpsPTheorem 3.6
Positive forward probability; EK−>EK+\mathbb{E}K^- > \mathbb{E}K^+; all positive moments finiteRDEFTheorem 4.1
Polynomial lower forward tail and some finite positive momentPTheorem 4.4
All positive moments infiniteP possibleTheorem D.1
Computable law⊆\subseteq RECTheorem 5.9
Position-dependent kernels
Monotone forward abilityCη,α⊆CDη,αC_{\eta,\alpha} \subseteq C_{D\eta,\alpha}Theorem 6.3
Parity clock: no returns / fixed β>0\beta> 0P / EXPTheorems 6.6 and 6.11
Doubling gates: forward-only / returns⊆\subseteq P / EXPTheorem 6.13
Density-zero backward-index support; return probability m−cm^{-c}, c>0c > 0, at 2m+12^m + 1EXPTheorems 6.15 and 6.16
Squaring gates: forward-only / returns⊆\subseteq P / 2EXPTheorem 6.18

Table 1. Selected fixed-confidence regimes, supplementing Figure 2. Each row holds for 0<α<10 < \alpha< 1; common-budget results are in Appendix F.

The relation between sums, maxima, and slowly varying tails is classical [13, 14]. The independent-sum limit theorem in Croydon–Fribergh–Kumagai [15, Section 5] is a relevant probability comparison. Here elementary proposal-maxima bounds suffice for the explicit tails used in § 5. The contribution is their realisation as fixed computable clocks with specified observation classes. The deterministic time hierarchy theorem supplies the strict separations between the familiar time classes [16 Section 3.1].

The sparse constructions address a different realisation problem. Their explicit laws have crossing radii that alternate between effective fast and slow stages. Finite rational searches protect all previously chosen slow stages from future atoms in the zero-drift construction. A partition of tower scales gives the negative-drift antichain. Distinguishing input cells supply accepting-time lower bounds, while specific length languages give witnesses above the bounded-prefix class. Thus the class comparisons are proved for the constructed laws; an arbitrary resource-function hierarchy alone does not provide those probabilistic realisations.

Restart strategies for Las Vegas algorithms use independent new runs [17]. Our phase-reuse argument instead changes accessibility within the clock on one fixed deterministic path. The deletion coupling compares forward-displacement laws, and the gates compare all forward-only members of specified kernel families. In the sparse gated examples, density and counting orders concern the support of backward indices in index space. They do not measure the frequency of backward moves along a trajectory. Vanishing probabilities are specified at the doubling landing indices (Theorem 6.16).

The fuzzy-time computation background is described in § 1.1.

Organisation

Section 2 defines the model and reachability dictionary; Sections 3 to 5 classify iid clocks, and Section 6 treats backward moves. Section 7 lists open problems. The appendices contain the sparse constructions, effectiveness proofs, calibrations, and common-budget results.

Model and the reachability dictionary

The jumpy observation model describes an observer who sees the configuration at a randomly chosen index, with consecutive indices chosen by a random clock that may jump. We define the computation path, clock, and acceptance rule. The access convention and sequential locality connect crossing estimates to language classes.

Machines, languages, and classes

The machine reads its input sequentially, which constrains clocks with small reach. We fix the machine conventions and recall the complexity classes used below.

A language over a finite alphabet Σ\Sigma is a set LL of finite input words; a machine decides LL when it halts and accepts exactly the words of LL. Polynomial time, written P, is the class of languages decidable with the number of executed transitions bounded by a polynomial in the input length. Exponential time is EXP =⋃k≥1DTIME⁡(2nk)= \bigcup_{k \ge1} \operatorname{DTIME}(2^{n^k}), with the usual asymptotic running-time convention. Equivalently, a language has a deterministic decider with bound 2p(n)2^{p(n)} for one fixed polynomial pp, after enlarging the bound to cover every input length. Doubly exponential time is 2EXP =⋃k≥1DTIME⁡(22nk)= \bigcup_{k \ge1} \operatorname{DTIME}(2^{2^{n^k}}). As for EXP, a language belongs to 2EXP exactly when it has a deterministic decider with bound 22p(n)2^{2^{p(n)}} for one fixed polynomial pp. For an integer k≥1k \ge1 put QPk=⋃c≥1DTIME⁡(2c(log⁡2(n+2))k)\mathrm{QP}_k = \bigcup_{c \ge1} \operatorname{DTIME}(2^{c(\log_2(n+2))^k}). Thus QP1=P\mathrm{QP}_1 = \mathrm{P}, and every QPk\mathrm{QP}_k is contained in EXP. The decidable languages are denoted REC, and the semidecidable (recursively enumerable) languages, accepted by machines that halt on yes-instances but need not halt on no-instances, are denoted RE. Thus P⊆REC⊊RE\mathrm{P} \subseteq\mathrm{REC} \subsetneq\mathrm{RE}. For example, over {0,1}\{0,1\}, the prefix language 101Σ∗101\Sigma^* is decided in three transitions, while Leven={x:∣x∣ is even}L_{\mathrm{even}} = \{x : |x| \text{ is even}\} requires a full input scan. The reverse-definite languages RDEF, defined below, depend on only a bounded initial segment.

Definition 2.1 (Machine and logical path) Fix a finite nonempty input alphabet Σ\Sigma. A machine has a finite tape alphabet Γ⊇Σ\Gamma\supseteq\Sigma and a blank b∈Γ∖Σb \in\Gamma\setminus\Sigma. Its tape has cells 1,2,…1,2,\ldots. Initially it contains x∈Σ∗x \in\Sigma^* in cells 1,…,∣x∣1,\ldots,|x| and blanks elsewhere. The head starts at cell 1 in a fixed state q0q_0, independent of xx. A transition reads and writes the scanned cell, changes state, and moves the head by −1-1, 00, or +1+1; a left move at cell 1 leaves the head there. Input access is sequential. There is no input-length oracle or free access to an end marker.

The transition function is deterministic and defined on every nonhalting state and tape symbol. There are distinct accepting and rejecting halting states qacc,qrejq_{\mathrm{acc}},q_{\mathrm{rej}}. We allow q0q_0 to be either halting state; this means that the machine halts before reading any symbol. A configuration records the state, head position, and full tape content. For each input xx, let

ρM(x)=(C0x,C1x,…)\rho_M(x) = (C_0^x,C_1^x,\ldots)

be the logical path obtained by executing transitions and repeating a halting configuration forever. The first halting index is TM(x)=inf⁡{i≥0:Cix is halting}T_M(x) = \inf\{i \ge0 : C_i^x \text{ is halting}\}, with inf⁡∅=∞\inf\varnothing= \infty. The first accepting index is AM(x)=TM(x)A_M(x) = T_M(x) if this halt accepts, and AM(x)=∞A_M(x) = \infty otherwise. Thus a rejecting halt has finite TM(x)T_M(x) but infinite AM(x)A_M(x); a nonhalting path has both indices infinite.

We use N={0,1,2,…}\mathbb{N} = \{0,1,2,\ldots\}. Budgets are polynomials Q:N→NQ : \mathbb{N} \to\mathbb{N} with nonnegative integer coefficients, including the zero polynomial. Every polynomial upper bound has a majorant of this form on N\mathbb{N}. We make the same enlargement for polynomial exponents in exponential-time bounds, taking p(0)≥1p(0) \ge1 when needed. Machine-model scope is discussed in Theorem 2.19.

The held walk and the access rule

The held walk defines an independent-proposal random clock, or fuzzy clock. One tick supplies a configuration under the following access rule.

Definition 2.2 (Law and held walk) Fix one probability law μ\mu on Z\mathbb{Z}, independently of the input and the machine. Let K1,K2,…K_1,K_2,\ldots be independent with law μ\mu. The logical position at tick tt is XtX_t, where

X0=0,Xt+1={Xt+Kt+1,Xt+Kt+1≥0,Xt,Xt+Kt+1<0.(1)X_0=0,\qquad X_{t+1}= \begin{cases} X_t+K_{t+1}, & X_t+K_{t+1}\ge0,\\ X_t, & X_t+K_{t+1}<0. \end{cases} \tag*{(1)}

An inadmissible negative jump is held at its starting position. This differs from the reflected update max⁡(0,Xt+Kt+1)\max(0,X_t+K_{t+1}); the held rule is not generally order-preserving between starting positions. For an integer target T≥0T\ge0, put

τT=inf⁡{t≥0:Xt≥T},inf⁡∅=∞.\tau_T=\inf\{t\ge0:X_t\ge T\},\qquad\inf\varnothing=\infty.

In the random-walk literature, τT\tau_T is the first passage time into [T,∞)[T,\infty). We write Pr⁡i\operatorname{Pr}_i for the same held walk started at i≥0i\ge0, and omit the subscript when i=0i=0.

Conventions. Configurations are supplied at unit access cost, and the observer tests whether the state accepts. Configuration generation, proposal sampling, and index writing are excluded from that cost. Laws and parameters are fixed in advance, with each parameter fixed throughout a run. Witnesses and budget constants may depend on the language, clock, and confidence. No effectiveness is assumed unless stated. These observation resources make no claim of a physical implementation or ordinary machine speedup.

Classical complexity charges transitions; the present access convention charges observations.

References

  1. [1]Michie, D.: “Memo” functions and machine learning. Nature 218, 19–22 (1968) https://doi.org/10.1038/218019a0
  2. [2]Chase, W.G., Simon, H.A.: Perception in chess. Cognitive Psychology 4(1), 55–81 (1973) https://doi.org/10.1016/0010-0285(73)90004-2
  3. [3]Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E.H., Le, Q.V., Zhou, D.: Chain-of-thought prompting elicits reasoning in large language models. In: Advances in Neural Information Processing Systems, vol. 35, pp. 24824–24837 (2022). https://doi.org/10.52202/068431-1800
  4. [4]Didehvar, F.: Theory of fuzzy time computation (TC* vs TC & TCQ). Manuscript, dated 1 January 2023. SSRN 4572734 (2023). https://doi.org/10.2139/ssrn.4572734 . https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4572734
  5. [5]Didehvar, F.: Theory of fuzzy time computation (TC* vs TC, edited version). Unpublished manuscript, dated 19 May 2026 (2026)
  6. [6]Zadeh, L.A.: Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems 1(1), 3–28 (1978) https://doi.org/10.1016/0165-0114(78)90029-5
  7. [7]Levin, D.A., Peres, Y.: Markov Chains and Mixing Times, 2nd edn. American Mathematical Society, Providence, RI (2017). https://doi.org/10.1090/mbk/107 . With contributions by Elizabeth L. Wilmer. Author’s version: https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf
  8. [8]Lindley, D.V.: The theory of queues with a single server. Proceedings of the Cambridge Philosophical Society 48(2), 277–289 (1952) https://doi.org/10.1017/S0305004100027638
  9. [9]Meyn, S.P., Tweedie, R.L.: Markov Chains and Stochastic Stability. Springer, London (1993). https://doi.org/10.1007/978-1-4471-3267-7 . Online edition recompiled in 2005. https://probability.ca/MT/
  10. [10]Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability 14(3), 502–525 (1982) https://doi.org/10.2307/1426671
  11. [11]Pemantle, R., Rosenthal, J.S.: Moment conditions for a sequence with negative drift to be uniformly bounded in L^r. Stochastic Processes and their Applications 82(1), 143–155 (1999) https://doi.org/10.1016/S0304-4149(99)00012-5
  12. [12]Hennie, F.C.: One-tape, off-line Turing machine computations. Information and Control 8(6), 553–578 (1965) https://doi.org/10.1016/S0019-9958(65)90399-2
  13. [13]Darling, D.A.: The influence of the maximum term in the addition of independent random variables. Transactions of the American Mathematical Society 73(1), 95–107 (1952) https://doi.org/10.1090/S0002-9947-1952-0048726-0
  14. [14]Kasahara, Y.: A limit theorem for sums of i.i.d. random variables with slowly varying tail probability. Journal of Mathematics of Kyoto University 26(3), 437–443 (1986) https://doi.org/10.1215/kjm/1250520877
  15. [16]Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009). https://doi.org/10.1017/CBO9780511804090
  16. [17]Luby, M., Sinclair, A., Zuckerman, D.: Optimal speedup of Las Vegas algorithms. Information Processing Letters 47(4), 173–180 (1993) https://doi.org/10.1016/0020-0190(93)90029-9
  17. [18]Durrett, R.: Probability: Theory and Examples, 5th edn. Cambridge University Press, Cambridge (2019). https://doi.org/10.1017/9781108591034 . Author’s version: https://math.duke.edu/~rtd/PTE/PTE5_011119.pdf
  18. [19]Brzozowski, J., Li, B., Liu, D.: Syntactic complexities of six classes of star-free languages. Journal of Automata, Languages and Combinatorics 17(2–4), 83–105 (2012) https://doi.org/10.25596/jalc-2012-083
  19. [20]Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Proceedings of the Symposium on the Mathematical Theory of Automata (New York, 1962). Microwave Research Institute Symposia Series, vol. 12, pp. 529–561. Polytechnic Institute of Brooklyn, Brooklyn, NY (1963)
  20. [21]Perles, M., Rabin, M.O., Shamir, E.: The theory of definite automata. IEEE Transactions on Electronic Computers EC-12(3), 233–243 (1963) https://doi.org/10.1109/PGEC.1963.263534
  21. [22]Kiefer, J., Wolfowitz, J.: On the characteristics of the general queueing process, with applications to random walk. The Annals of Mathematical Statistics 27(1), 147–161 (1956) https://doi.org/10.1214/aoms/1177728354
  22. [23]Hoyrup, M., Rojas, C.: Computability of probability measures and Martin-Löf randomness over metric spaces. Information and Computation 207(7), 830–847 (2009) https://doi.org/10.1016/j.ic.2008.12.009 . Author’s version: https://members.loria.fr/MHoyrup/random_metric.pdf
  23. [24]Radó, T.: On non-computable functions. The Bell System Technical Journal 41(3), 877–884 (1962) https://doi.org/10.1002/j.1538-7305.1962.tb00480.x

Paper details

vlnc:W_qcmtatsh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents