[jayd16]

>In fact, no finite amount of computation will guarantee that we will be able to tell whether x=0 or x>0

Hmm, I'm still stuck at this assertion. Why can we not assume the number is finite?

If we assume an infinitely long number takes an infinite amount of time to read, can we not also assume it must take an infinite amount of time to write? If we only have finite time, can we not assume all numbers given to the function in that time are finite?

[afc]

Yeah, I'm also stuck here.

The article seems to say that, because you can't produce an upper bound to the amount of time the sgn function will take to run (for all possible inputs), sgn isn't a function. But then... isn't it the same for every single other function?

I think the article is conflating "given a fixed amount of time, one can find an input for which the function will take longer to run" with "the function takes infinite time". The later isn't true: for any given input, no matter how big, one can compute a time such that the function will finish in that time; in other words, the function always finishes, in finite time, for every possible input, no matter how large.

It's possible we're both confused, I suppose. :-)

[Ericson2314]

Here's the thing: the "discrete vs continuous" most people were taught is wrong. Discrete is [can always be construed as] continuous. Only infinite things can be discontinuous.

State is finite but time is countably infinite for our purposes, so we model infinite/unbounded things with programs that can run arbitrary long.

Finally, this abstract math stuff is in fact a really good UI point that most programmers miss. In non "real time" applications, you should aim to be able to dynamically tradeoff tardiness and richness; e.g. a fancy diagram that is rendered at low res and then higher res. Likewise all your caches should be evictable under memory pressure. Computing should feel fluid.

It's a pity most people only paleolithic state machine math or terminating thing math. This falsely implies that "real world programs" which hardly ever terminate are beyond theory, or that the smartypants thing to do is break them down into little terminating programs and some big spooky event loop whateverthefuck (browser, apache, framework du jour, etc etc.). Build codata out of codata!

[Retric]

How would you turn f(x != 1) = 0, f(1) = (has no value) to be continuous?

Because it sounds like you’re simply redefining the terms. At which point you might as well be using “Spork”. Because, defining a new system has zero impact on a different system.

[Ericson2314]

1. You are talking about partial functions, that is a separate concern.

2. Behold https://en.wikipedia.org/wiki/Discrete_space . Topologies define continuinity, and here is a discrete topology.

3. With e.g. probability measures / expected values, which unify "discrete" and "continuous" statistics, you'll notice that there's lots of rules that are trivially obeyed in the discrete case, but take some care in the "continuous" case. For example, not ever set can have a measure in the latter but can in the former. This directly relates to discrete things being trivial to deem continuous. It's also a useful to define coarser topologies / event sigma-algebras in the finite case to better understand the issues are the unavoidable in the infinite cases. We only make the discrete discontinuous in that last "artificial" exercise.

[GolDDranks]

I believe that the function you just defined is already continuous. It's not defined at 1 so checking its continuity doesn't make sense there, and at every other point it's clearly continuous because it's constant. Points that are arbitrarily close to 1 are still continuous because the intervals around 1 are open.

[Retric]

In calculus f(x) = x/x - 1 is not continuous at 1 based on the initial definitions. Moving to fixed-point arithmetic the idea of limits gets odd, but the function still needs a definition for that input.

[GolDDranks]

I would say the continuity isn't just defined at that point... I very much agree that one can't affirmatively say that the function is continuous at that point. Btw. I guess you meant to say f(x) = (x - 1)/(x - 1).

However, let's ignore that; the problem disappears if we define f(x ) = 1 at x = 1, and f(x) = 0 elsewhere.

In standard analysis that function would be discontinuous at that point.

I'm not sure about implications in the OP's kind of analysis. Would the existence of m(1) imply that there exist some smallest input that is larger than 1, that would make difference in output? Same for the largest input that is smaller than 1.

[tel]

You handle continuity in discrete spaces through topology. A function is continuous for a (really, two) given topology if the inverse images of open sets are open sets.

[GolDDranks]

That specific function can take infinite time to decide whether the input x belongs in the case x < 0, x = 0 or x > 0. The problem manifests itself if we allow x to be a true real number. As you surely know, real numbers may have infinite amount of digits after the point, and if we get a real 0.00000000000... as the input, we must continue inspecting it, until we can be sure about which case it belongs to. But because that real might contain infinite amount of information, we might never finish!

[afc]

I disagree, how interesting. :-)

I presume that you're allowing finite time execution of the equality-to-zero operation (I.e., a function that says if a number is equal to zero). If you don't, I suppose one would conclude (by applying the same arguments, whatever they are) that neither can a function that, say, adds numbers or does similarly trivial operations finish in finite time, in which case this distinction of finite- vs infinite-runtime functions isn't very interesting.

Any number that isn't zero and that starts with a zero (at the left of the dot), will always have a finite number of zero digits after the point. In other words, the only number that has a zero at the left of the dot (i.e., of the form 0.xyz...) that has an infinite number of zero decimals is zero itself.

I guess where we disagree is in this claim: "As you surely know, real numbers may have infinite amount of digits after the point". The only real numbers with this property are the integers. Every other real number has to have a finite number of zeros.

[edflsafoiewq]

Here's a more practical definition than "a stream of digits". A computable real representing the real number x is a program that takes as input a rational ϵ>0 and produces as output a rational number within ϵ of x. That is, it produces approximations to x to any desired level of precision.

Every rational q is computable: λϵ.q

The sum of two computable reals, x and y, is computable: λx,y.λϵ.x(ϵ/2)+y(ϵ/2)

You can show the absolute value function is computable: λx.λϵ.|x(ϵ)|

So there are many trivial continuous functions like addition that are computable.

But the discontinuous function f(x)=1 if x=0, f(x)=0 otherwise, is not computable.

[danharaj]

A program that takes an integer n and outputs the n'th digit of the number it represents is a finite representation of an infinite stream of digits.