[HN Gopher] The halting problem is decidable on a set of asympto...
___________________________________________________________________
The halting problem is decidable on a set of asymptotic probability
one (2006)
Author : Schiphol
Score : 104 points
Date : 2023-05-28 16:52 UTC (6 hours ago)
(HTM) web link (projecteuclid.org)
(TXT) w3m dump (projecteuclid.org)
| dgacmu wrote:
| In case anyone wants a quick tl;dr: as the length of a program
| (expressed as the number of states in a Turing machine) grows,
| the relative fraction of undecidable programs decreases. In other
| words, "most" (approaching "nearly all" as they get longer)
| Turing machines, out of the set of all possible Turing machines
| of that same size, are actually decidable. (Though this doesn't
| tell us about whether most real programs are decidable, as the
| programs humans write also come from a small subset of the
| universe of Turing machines. But we know that in practice, this
| is also true).
|
| This relates nicely to the earlier discussion of SAT: while SAT
| is NP-complete, many instances can be solved in reasonable time.
| Similarly, we can verify that many actual programs will halt even
| if the problem is, in general, undecidable.
| turminal wrote:
| The difference with SAT is that for SAT we actually know the
| opposite is true - the instances that can be solved quickly are
| the "rare" kind.
| bawolff wrote:
| I think it would be pretty shocking if the opposite were true.
| I imagine most randomly generated turing machines are pretty
| trivial.
| EscapeFromNY wrote:
| My intuition tells me the opposite.
|
| Suppose you have one undecidable statement, U, out of s
| possible statements. A random program of length n contains U
| at least once with probability 1-(1-1/s)^n. If the program is
| of infinite length, it contains U with probability 1. So I
| would have thought the chances of undecidability _increase_
| as the program gets longer.
|
| Clearly my intuition is _wrong_ , per the paper, but I don't
| think the result is immediately obvious.
| cyberax wrote:
| Think about it like this, there are infinitely many Turing
| machine state classes that are easily decidable. For
| example, a simple infinite loop or its equivalent. Most of
| these classes are also very trivial to construct, and
| require only a few "instructions".
|
| So if you make a random TM, it's almost guaranteed that
| it'll get eventually "trapped" in one of these easily
| decidable infinite loops.
| EscapeFromNY wrote:
| Thanks, that's a perfect explanation
| bawolff wrote:
| I think the chance of having an undecidable (group of)
| statements go up, but the chance of executing it does not.
|
| There isn't really a single undecidable statement, it would
| be a complex subroutine. My intuition would be its much
| more likely a halt or indef loop (both relatively simple)
| would appear before program control would transfer to the
| undecidable part, in most cases.
|
| I.e. if something undecidable requires 60 symbols in a row
| in correct order, but halting requires one, than
| probability of a halt at any given spot seems much higher
| on average.
| zeroonetwothree wrote:
| A statement in a program can't really be undecidable on its
| own. It's the program that has that property.
| chromoblob wrote:
| A statement is just a subprogram. Whether it can be
| decidable depends on whether a single program can be
| undecidable (and I can't see how that could be possible,
| undecidability is property of the problem - decision
| procedure on _set_ of programs)
| mananaysiempre wrote:
| Dunno. The real numbers, for example, are in the "most things
| are eldritch abominations" camp[1]: the reals are
| uncountable, the _computable_ reals are a(n everywhere dense)
| countable set[2] (that is therefore[3]) of measure zero. Not
| that there's a reason to expect these cases to be similar,
| just that weird things do happen.
|
| [1] https://mathwithbaddrawings.com/2016/12/28/why-the-
| number-li...
|
| [2] There's a finite set of programs of a fixed length, thus
| (countable union of finite sets) a countable set of all
| programs, thus only at most a countable set of numbers they
| can compute.
|
| [3] Every countable set has Lebesgue measure zero: cover
| point #n by a blot of measure e / 2^n (that could even
| intersect other blots) to prove all of them have measure at
| most e > 0, take e as small as desired.
| fpoling wrote:
| The notion of uncountable set assumes certain axioms and
| classical logic. If instead one assumes rules of
| constructive mathematics, then one cannot construct
| uncountable set. Simplifying only computable numbers can
| exist.
| mananaysiempre wrote:
| Note that there are multiple versions[1] of "constructive
| mathematics", so for example what Bishop's constructive
| real analysis book considers constructive is not what
| Markov's "constructive = computable" tradition does.
|
| You are also going to encounter other funny things. One
| of De Morgan's laws failing could seem troubling but
| ultimately theoretical--how, then, about the distinction
| about countable and _constructively_ countable[3]? The
| set of all programs is countable; the set of all
| _terminating_ programs is a subset of it, but can't
| constructively be proven to itself be countable--after
| all, that would imply a solution to the halting problem!
| (Neither can it constructively be proven to _not_ be
| such, as it _is_ such in a consistent extension, namely
| classical mathematics.) Thus you get the new and exciting
| notion of _subcountable_ sets. And that's one of the
| mildest things that you're going to encounter in your
| shiny new theory of cardinals.
|
| (Anybody who can explain to me what the hell constructive
| Hahn--Banach[4] is about gets a beverage of their choice
| if we are ever in the same city. Without HB, you cannot
| do any functional analysis worth a damn, and without that
| you can't really talk about Green's functions /
| fundamental solutions to linear PDEs, which are in turn a
| basic tool for any electodynamics or quantum mechanics
| worth speaking about. Unless you want to forgo proof or
| the natural sciences, you need it, is my point.)
|
| None of this is to say that I think intuitionistic logic
| is useless, mind you. It's interesting and useful[5]! But
| so far it seems that you need to learn at least some
| logic (as a piece of mathematics and not mere
| terminology, so including scary words like "metalogic")
| before you can really understand how it comes together.
|
| [1] It seems categorical logic[2] says useful things
| about what the One True Definition should be? But I don't
| understand it well enough to tell, and in any case the
| constructivist tradition predates not only it but
| category theory in general.
|
| [2] https://mikeshulman.github.io/catlog/catlog.pdf
|
| [3]
| https://ncatlab.org/nlab/show/constructive+mathematics
|
| [4] https://www.cse.chalmers.se/~coquand/hahn1.pdf
|
| [5] https://www.ams.org/journals/bull/2017-54-03/S0273-09
| 79-2016...
| agalunar wrote:
| > the distinction about countable and constructively
| countable? The set of all programs is countable; the set
| of all terminating programs is a subset of it, but can't
| constructively be proven to itself be countable--after
| all, that would imply a solution to the halting problem!
|
| I thought this had to do with the difference between
| being computable and computably enumerable.
| orlp wrote:
| I've made the argument many times before that the reals are
| certainly an interesting set of objects, but a poor
| abstraction for the concept of a number. We should work
| towards replacing them with a more well-behaved set without
| eldritch monsters such as uncomputable 'numbers' that you
| can't add or multiply with. E.g.
| https://en.wikipedia.org/wiki/Computable_number.
| mananaysiempre wrote:
| There's a tradeoff[1] throughout mathematics, not unlike
| the expressiveness--analyzability one in programming
| languages: either the _set_ of things you're working with
| has nice properties (e.g., for the reals, completeness)
| and supports nice constructions with no caveats (e.g.,
| for the reals, limits); or each of the _things_ in the
| set is individually nice and tractable (e.g. computable).
|
| There isn't a single universally appropriate choice here,
| and sometimes even the direction of the axis is not
| obvious (real numbers lack solutions for algebraic
| equations; complex numbers lack smooth functions nonzero
| only in a finite region), but usually a simple family of
| eldritch objects is easier to deal with than an byzantine
| clan of cuddly objects.
|
| Could you do simple physics and more generally ordinary
| differential equations over the computable numbers? You
| _probably_ could to some extent, but it's unlikely you'd
| get the nice intuitive geometry you get over the reals
| (see e.g. Arnold's ODE textbook). The (basic) geometry of
| surfaces parametrized by real coordinates is fairly
| straightforward (differential geometry); the geometry of
| surfaces parametrized by _rational_ coordinates is
| famously mind-blowingly abstract (algebraic geometry).
| The (basic) theory of real or complex functions is mostly
| understandable (analysis); the theory of natural or
| rational functions is _horrifying_ (number theory).
|
| Also, as a sibling reply mentions, it's not like
| computable numbers will solve every problem: even though
| arithmetic over them is decidable, order still isn't, and
| computable transcendental functions aren't exactly a
| cakewalk either.
|
| It doesn't mean the computable reals aren't worth knowing
| about, but, well, we live in a world where mandatory
| education has violently rejected[2] every advance in
| mathematical thought since Otto von Bismarck left office,
| and reduced the ones it accepted to a desiccated husk[3],
| so there are a great many things in that category. (I
| cannot help but remember the SMBC patriotism vs
| nationalism comic[4]: "Now I am mathematics.")
|
| [1] https://ncatlab.org/nlab/show/dichotomy+between+nice+
| objects...
|
| [2] http://www.ams.org/notices/201201/rtx120100031p.pdf
|
| [3] https://www.maa.org/external_archive/devlin/devlin_03
| _08.htm...
|
| [4] https://www.smbc-comics.com/comic/an-important-
| distinction
| zeroonetwothree wrote:
| Computable functions do also have some weird behavior.
| For example: a) all functions are continuous, b) equality
| is not computable (maybe not so weird for anyone used to
| floating point), c) differentiation is not computable
| unless you work over complex numbers (but integration
| is!)
| orlp wrote:
| a) All functions from computable reals to computable
| reals are continuous. This makes sense, because an
| arbitrarily small input difference leading to an
| arbitrarily large output difference is not a good basis
| for computation. You can still have discontinuities for
| discrete computable maps.
|
| b) Neither is equality computable for the reals. Nothing
| is lost here.
|
| c) Differentiation is computable for the functions of
| computable reals if you have a computable rate of
| convergence.
| chromoblob wrote:
| How to do (c)? I tried to model the reals as lazily
| computed sequences of intervals with rational bounds
| where every next interval is subset of previous one, and
| couldn't write a higher-order differentiator function
| because on every step for a given input interval there is
| output interval with non-zero (in most cases) size and
| the differentiated function may contain quick enough
| oscillations that the derivative is unbounded, and thus
| the derivative will stay unbounded no matter what you do.
| What do you mean by rate of convergence?
| orlp wrote:
| https://en.wikipedia.org/wiki/Modulus_of_convergence
| passion__desire wrote:
| tl;dr : Maybe the reals are far more mysterious. All we
| ever have handle over are the countable sets.
|
| [0] Looking back, the core of my confusion was this. I had
| thought: I can visualize what 0 means; that's just the
| infinity of integers. I can also visualize what C=2^0
| means; that's the infinity of points on a line. Those,
| therefore, are the two bedrocks of clarity in this
| discussion. By contrast, I can't visualize a set of
| intermediate cardinality between 0 and C. The intermediate
| infinity, being weird and ghostlike, is the one that
| shouldn't exist unless we deliberately "force" it to.
|
| Turns out I had things backwards. For starters, I can't
| visualize the uncountable infinity of real numbers. I might
| think I'm visualizing the real line--it's solid, it's
| black, it's got little points everywhere--but how can I be
| sure that I'm not merely visualizing the 0 rationals, or
| (say) the computable or definable reals, which include all
| the ones that arise in ordinary math?
|
| The continuum C is not at all the bedrock of clarity that
| I'd thought it was. Unlike its junior partner 0, the
| continuum is adjustable, changeable--and we will change it
| when we build different models of ZFC. What's (relatively)
| more "fixed" in this game is something that I, like many
| non-experts, had always given short shrift to: Cantor's
| sequence of Alephs 0, 1, 2, etc.
|
| [0] https://scottaaronson.blog/?p=4974
| EGreg wrote:
| Also the same applies with the CAP theorem... it is mostly a
| theoretical result but in practice things go well the vast
| majority of the time!
|
| Also look up Buridan's Principle by Leslie Lamport. I emailed
| him and "argued" with him for a while after reading his paper,
| but in a theoretical sense and some practical subsets it is
| correct!
| sebzim4500 wrote:
| Interesting paper. I agree that he is probably technically
| correct, but I think he downplays the fact that all over
| physics people say "never" when they mean "with probably less
| than 10^-1000.
|
| For example, in classical thermodynamics there is a nonzero
| probability that all the air molecules in a room will happen
| to travel to one side, violating many laws of fluid
| mechanics. In quantum mechanics the situation is even worse,
| where basically anything can happen with nonzero probability.
| SilasX wrote:
| I'm not sure the comparison to SAT is a good one because, in
| that case, we know of particular "phase transition" regions in
| which most problems _aren't_ clearly satisfiable or
| unsatisfiable. (Specifically, when the ratio of clauses to
| variables in 3SAT is about 4.2.)
| oldgradstudent wrote:
| It's an excellent comparison to SAT, because in both cases
| nobody cares about random instances at all.
|
| For non-random instances the ratio of clauses to variables in
| is utterly meaningless.
| zeroonetwothree wrote:
| The simplex algorithm is similar being exponential time worst
| case but in practice often closer to linear
| adamnemecek wrote:
| No one talks about the fact that the halting problem has been
| solved for linear bounded automata.
| russdill wrote:
| Because it's immediately obvious that for anything with a
| finite number of states determining if it runs forever is
| "trivial" as running it until it either repeats a state or
| halts which will always occur in finite time.
| adamnemecek wrote:
| Right, why are there so few total languages then?
| amelius wrote:
| Uh, yeah, but my PC with 96GB of memory has quite some
| possible states.
|
| So, most likely, the _real_ reason nobody is interested is
| that the numbers are too large.
| Jeff_Brown wrote:
| It's an interesting result, but the probability distribution
| seems to be doing a lot of the work. The distribution of programs
| a human is likely to encounter is very different from the set of
| all programs of length N uniformly distributed.
| isaacfrond wrote:
| The problem is that with probability 1 a random problem will
| access an undefined memory position. Such program halt by
| definition.
|
| This makes the result a lot less interesting. Sure random
| programs will typically halt before long, but with an illegal
| memory access ( in the parlance of the article, they read from
| the left of the turing tape)
| l33t233372 wrote:
| There is no such notion of "undefined memory region" for a
| Turing Machine
| thelopa wrote:
| Some models of the Turing machine have an infinite tape in
| only one direction. Some also don't require every state to
| have an exhaustive set of transitions. Those models generally
| consider going off the end of the tape or failing to find a
| transition to be a halting state.
| l33t233372 wrote:
| It's unclear to me why restricting ourselves to that model
| is useful here
| fooker wrote:
| It's the simplest model which can simulate _all_ useful
| models of computation we have so far.
|
| So, if you want to prove something about the limits of
| computation, a Turing machine is usually the right
| choice.
| knome wrote:
| Changing the model wouldn't change anything. A turing
| machine is equivalent to any computational machine you
| want to put in there. It doesn't matter what the machine
| is. The turing machine is the goto because it was first
| used for them.
|
| Any other machine that can simulate a turing machine can
| simulate failing in those same ways. You can't escape the
| problems of turing completeness without losing it.
| mgraczyk wrote:
| It does matter, the second and last sentence of the
| abstract is "The proof is sensitive to the particular
| computational models."
| mgraczyk wrote:
| It is true that some models define halting that way, but in
| this paper they explicitly do not.
| tromp wrote:
| The paper makes explicit how this is dealt with:
|
| > For the purposes of defining the halting problem H, one
| should specify whether it officially counts as halting or
| not if the head should happen to fall off the left edge of
| the tape. Although the truth of the main theorem will not
| depend on these details, provided we adopt a uniform
| answer, let us be definite and regard such computations as
| having not officially halted, as the halt state was not
| reached.
| mgraczyk wrote:
| This is wrong and directly contradicted, unambiguously by the
| linked paper.
|
| "For the purposes of defining the halting problem H, one should
| specify whether it officially counts as halting or not if the
| head should happen to fall off the left edge of the tape.
| Although the truth of the main theorem will not depend on these
| details, provided we adopt a uniform answer, let us be definite
| and regard such computations as having not officially halted,
| as the halt state was not reached."
| credit_guy wrote:
| This contradicts Murphy's theorem, that if something can go bad
| it will go bad with asymptotic probability one.
| klyrs wrote:
| No, Murphy says that despite having a vanishingly small
| probability, somebody will toss an undecidable problem into
| your non-halting oracle.
| zeroonetwothree wrote:
| I would say it's consistent since something going bad can often
| mean halting
| falcor84 wrote:
| Well, if the program is operating a business-critical function,
| then having it halt is bad.
| eterevsky wrote:
| A few years ago I had an idea to try and solve halting problem
| for as many Brainfuck problems as possible, using a few simple
| heuristics. (To make things easier I picked a dialect with 1 byte
| cells that weren't allowed to over- or underflow.)
|
| I managed to solve all BF programs up to length 12. The longest
| running but stopping short program that I've found was this:
| >+[>++>+++[-<]>>], it stopped after 9212 steps.
|
| https://github.com/eterevsky/beaver
| saghm wrote:
| From what I recall, the "undecidable" part of the halting
| problem isn't determining that something halts, but determining
| that it _doesn't_ halt (i.e. the halting problem is verifiable,
| as opposed to the inverse "non-halting" problem, which isn't
| verifiable, which is always the case for the inverse of a
| verifiable problem).\
|
| I've never properly learned brainfuck, so the answer to this
| might be trivial without needing to write a solver, but what's
| the shortest non-halting program you found?
| shoo wrote:
| The shortest non-halting brainfuck program will have exactly
| three instructions. Here is one them: `+[]` here is another
| one: `-[]`.
|
| Brainfuck's state consists of an array of integers, an index
| into that array, a program counter, and some bookkeeping
| required to track which "[" corresponds to which "]".
|
| Let's assume the array a[:] is zeroed and the index i is set
| to 0 before the program begins executing.
|
| Then `+` increments the cell in the array a at index i, i.e.
| `a[i] += 1`; `[` begins a while loop, equivalent to `while
| a[i] != 0 {`; and `]` ends the while loop: `}` .
|
| So the program `+[]` is equivalent to something like
| a := (allocate a length N array of bytes, set to zero)
| i := 0 a[i] += 1 while a[i] != 0 { }
|
| which will not terminate.
|
| Why is this the shortest?
|
| `]` is the only instruction that might decrease the program
| counter, otherwise the program counter always increases by
| one or more. Therefore, a non-halting brainfuck program must
| include at least one `]`. Brainfuck programs are
| syntactically incorrect unless there is exactly one `]`
| occurring somewhere in the program after each `[`. So the
| shortest non-halting brainfuck program must have at least two
| instructions.
|
| There is only one syntactically valid brainfuck program with
| two instructions that might not halt: `[]`. But this will
| halt, assuming that the array `a` is initialised to zero
| before execution begins. So the shortest non-halting
| brainfuck program contains three instructions.
| LegionMammal978 wrote:
| To add to this, there is also the `,[]` program, which
| reads a single input byte, halts iff it is zero, and loops
| infinitely otherwise.
| shoo wrote:
| Fair point! Arguably the program `,` might not halt if a
| user never provides a byte of input to read! I've never
| seen a brainfuck machine with a read timeout.
| lmm wrote:
| > I've never properly learned brainfuck, so the answer to
| this might be trivial without needing to write a solver, but
| what's the shortest non-halting program you found?
|
| It's a pretty trivial question in any language, it tends to
| just be while(true); or similar in that language.
| nixpulvis wrote:
| What is it in the lambda calculus?
| [deleted]
| tromp wrote:
| > I managed to solve all BF programs up to length 12.
|
| With 8 possible instructions, that is equivalent to all
| programs up to 12 * log 8 = 36 bits. Curiously, that _exactly_
| matches how far we were able to analyze the behaviour of a
| functional busy beaver [1].
|
| > it stopped after 9212 steps.
|
| The largest output of a 36 bit lambda term is a whopping 578960
| 446186580977117854925043439539266349923328202820197287920039565
| 648199686 bits long though...
|
| [1] https://oeis.org/A333479
| l33t233372 wrote:
| I've never seen "asymptomatic density" referred to as
| "asymptomatic probability."
|
| Anyways, if anyone is interested is a more complete survey of
| similarly flavored computability/density results, this paper is
| good:
| https://faculty.math.illinois.edu/~jockusch/DensityCE_JML.pd...
|
| There is even some pure combinatorics involved, for example I
| remember lemma 6.7 from my combinatorics class back in undergrad
| meithecatte wrote:
| Note: it's not asymptomatic, but asymptotic - without the ma. I
| can only wonder whether you've always been writing it like
| that, or if this is the toll that the pandemic had on you.
| aklein wrote:
| Maybe they just need a vaccination... uh I mean a vacation
| tromp wrote:
| The meat of the paper is this short
|
| > Proof of the Main Theorem Using the standard model
|
| > let B be the set of programs that on input 0 either halt before
| repeating a state or fall off the tape before repeating a state.
| Clearly, B is polynomial time decidable, since we need only run a
| program p for at most n steps, where n is the number of states in
| p, to determine whether or not it is in B. It is equally clear
| that the halting problem is polynomial time decidable for
| programs p in B, since again we need only simulate p for n steps
| to know whether it halted or fell off. What remains is to prove
| that this behavior occurs with asymptotic probability one.
|
| The proof also makes use of this
|
| > Lemma 2.5 (Polya [2], see also, e.g., [1])
|
| > In the random walk with equal likelihood of moving left or
| right on a semi-infinite tape, beginning on the left-most cell,
| the probability of eventually falling off the left edge is 1.
|
| This suggests that the result crucially depends on having a one-
| sided infinite tape rather than the two-sided infinite tape
| that's used in the Turing Machine busy beaver.
|
| It would be interesting to determine whether the result also
| holds for that other computational model, i.e. what about the set
| of lambda calculus terms with or without a normal form?
| jameshart wrote:
| Similarly, as the number of particles in a system increases, the
| less you have to worry about Heisenberg uncertainty bounds on
| your momentum/position measurements.
|
| It's a misreading of the halting problem to think of it as a
| 'barrier' of some sort. What it really means is that there are
| some computer programs where the only way to find out what they
| will do is to actually run them. There's not a 'better trick' you
| can pull to get the answer. This is kind of intuitive, since we
| know there are problems we run into where the easiest way we can
| think of to solve them is to write a program and run it. The
| halting problem tells us that it's plausible that that instinct
| is right - that for some programs, you really can't do some other
| analysis of the program that tells you what it's going to do. You
| have to just run it.
|
| Like: take a random complex number with magnitude < 2. Keep
| squaring it and adding the original number. Will you ever get a
| number with magnitude > 2?
|
| For some numbers you can take a shortcut and say yes or no. But
| for others the only way to find out is to keep doing it.
| qubex wrote:
| I think you're confusing computational irreducibility and the
| halting problem.
| mgraczyk wrote:
| > The halting problem tells us that it's plausible that that
| instinct is right - that for some programs, you really can't do
| some other analysis of the program that tells you what it's
| going to do. You have to just run it.
|
| This isn't quite right. The halting problem says that you can't
| just run it. If you just run it, you will not learn whether or
| not it halts after any finite amount of time.
|
| Also I don't see how this is related to uncertainty bounds.
| ttctciyf wrote:
| > If you just run it, you will not learn whether or not it
| halts after any finite amount of time.
|
| If it halts within a finite amount of time, you will.
| amelius wrote:
| But that is not the only possibility. So you are missing
| the point.
| saghm wrote:
| > Similarly, as the number of particles in a system increases,
| the less you have to worry about Heisenberg uncertainty bounds
| on your momentum/position measurements.
|
| This certainly makes intuitive sense, since it explains why we
| don't have trouble measuring both the speed and position of
| objects in everyday life with fairly high precision.
| Y_Y wrote:
| What does this have to do with Heisenberg uncertainty?
| teaearlgraycold wrote:
| Unexpected Mandelbrot
| nico wrote:
| Is there a contest somewhere for the longest continuously-running
| computation?
|
| It would be interesting to see how long we are capable of running
| even just a while true
|
| The power might go out, some electronic component might fail, or
| the cooling system, etc
|
| What is the longest that we are actually capable of keeping the
| most simple system running?
| odo1242 wrote:
| Probably Voyager 2. Running since August 20, 1977 - never been
| rebooted (because good luck doing that)
| schoen wrote:
| Maybe there's a clock on Earth with a microcontroller and
| some kind of UPS or battery backup or large capacitor backup?
|
| You could argue that the timekeeping of TAI
| (https://en.wikipedia.org/wiki/International_Atomic_Time)
| could be seen as a distributed computation (where different
| entities are counting the same value and running manual and
| automated protocols to keep the value synchronized), and that
| has been running since 1972. It almost certainly hasn't been
| running continuously on any individual hardware device, but
| there have always been devices that represented its value and
| always been efforts to maintain continuity between
| calculations.
|
| Although I guess the same logic could argue for civil
| timekeeping in _any_ calendar, because people have actively
| tracked it as "the same computation" and cared about it for
| centuries or millennia. Maybe the distinctive argument for
| TAI is that it's presumably been continually _represented
| digitally in programmable computers_ since 1972.
| jgtrosh wrote:
| Does the century old continuously running lamp bulb in a fire
| brigade count as a computation, if a while true does?
| mannykannot wrote:
| Life on Earth is an out-of-equilibrium process that has been
| running for ~3.5 billion years.
___________________________________________________________________
(page generated 2023-05-28 23:00 UTC)