On: How to publish Git repos that cannot be republishe...

[mannykannot]

Ha! - but I don't think it is physically possible to publish a transcendental number, is it? (Nor any other non-rational real?)

[moomin → mannykannot]

Depends what you mean. If it can be specified by a finite sequence of operations, I’d say it’s publishable.

If you’re going to restrict “publishing” to binary fixed point, arguably 1/3 is unpublishable.

[schoen → moomin]

The real (no pun intended!) distinction is between computable and noncomputable reals, as first identified by Alan Turing in "On Computable Numbers".

The integers are a subset of the rationals, which are a subset of the algebraic numbers, which are a subset of the computable numbers, which (most mathematicians would accept) are a subset of the reals.

There are lots of subtleties about this. In fact Scott Aaronson just started a series that is in some sense about some of those subtleties, which I hope to be able to understand some day!

[mannykannot → moomin]

> If it can be specified by a finite sequence of operations...

Hmm... are you saying that, for example, pi is the one-step sequence of operations of dividing a circle's circumference by its diameter? But first, you have to get both those values...

[tsimionescu → mannykannot]

There are simple formulas for computing Pi. For example Pi can be computed to arbitrary precision as 4 * (1 - 1/3 + 1/5 - 1/7...).

[lopmotr → mannykannot]

An algorithm for computing pi would be a finite sequence of operations. Even if the operations include "do an infinite loop".

[eru → lopmotr]

Pedantically enough, by formal definitions algorithms have to finish. See eg https://en.wikipedia.org/wiki/Algorithm

In practice, speaking informally, people talk about programs that may run forever all the time.

People have developed lots of theory around those as well. Of specific interest here would be the class of programs that provably only runs for a finite time before it produces the next bit of output.

You need that latter class of programs to talk about producing digits of pi, or running the main loop of an OS.

See also https://en.wikipedia.org/wiki/Total_functional_programming

[mannykannot → lopmotr]

Then, I would say, you would be publishing a fact about pi, not pi itself. These facts do not yield pi in any finite time.

[bregma → moomin]

I'm confused by how you could specify a transcendental number using a finite sequence of operations. It's sort of in the very definition of transcendental numbers that you can't.

[roywiggins → bregma]

You could just write down a Turing machine.

That captures all of the transcendentals we care about. The remainder (to be fair, almost all of them) aren't computable at all, even in principle.