Program a mathematical function

Computer Science Level 4

Suppose you have a programming language $\mathcal L$ designed to efficiently perform calculations with real numbers. In particular, it allows for the definition of (computational, deterministic) functions which take one number as an argument and return a number:

1
2
3

define F(x):
   y = ...;
   return y;

Let $f:\ \mathbb R \to \mathbb R$ be an arbitrary mathematical function, mapping real numbers to real numbers. What is the probability that $f$ can be modeled using a function programmed in $\mathcal L$ ?

Assume that $\mathcal L$ can handle real numbers in an arbitrarily large range, with infinite precision. The programmed function $F$ is of finite length.

almost, but not quite, 100% 0% extremely small 100% around 50%

1 solution

Arjen Vreugdenhil
Jul 4, 2019

The probability is 0%.

Since every program has finite length, the number of programs that could be written is countably infinite, corresponding to a countable set of points $\mathcal C$ in $\mathbb R^{\mathbb R}$ . For any integer $n$ , the disjoint union of $n$ copies of $\mathcal C$ is still only countable, strictly smaller than $\mathbb R^{\mathbb R}$ , showing that $n\mathbb P \leq 1$ for every integer $n$ . Therefore the probability is $\mathbb P = 0$ .

A less formal thought about this: taking further into account that there are no restricitons to bijectivity, differentiability, steadyness or even a logic (mathematical) relation, the amount of functions that are representable in the limited mathematical language (in the >best< case, not in reality, this is also the limit of the programming language) compared to all possible functions, is just like a grain of sand in the universe.

Eric Scholz - 1 year, 11 months ago

You did not allow for "of measure zero".

A Former Brilliant Member - 1 year, 11 months ago

What do you mean? "0%" is a probability measure of zero.

Arjen Vreugdenhil - 1 year, 11 months ago

See your own argument above. It only shows that the limit of the probabiIity that a finite program exists that can make a specific mapping from $\mathbb{R}$ to $\mathbb{R}$ is $0$ . I am making the distinction similar to the distinction between a function's value at a argument value, say $\theta$ which may be indeterminate and the limit of that function's value as its argument goes to $\theta$ which could be determinate. That is, the limit of the probability is 0. You did not offer that answer.

A Former Brilliant Member - 1 year, 11 months ago

Program a mathematical function

1 solution

0 pending reports