30:T47b,md`Intuitively, the algorithm is bounding the function at ${tex`t=${q}`} by little arcs of *rational functions* from above and below, within the given precision ${tex`${e}`}. It may seem over-complicating matters, but it is partly with defining continuity and differentiability in mind, and partly to elevate rational functions as first-class citizens while demoting Dirichlet's function and other "pathological" examples in classical analysis. What is the order on ${tex`\mathbb Q(t)`} at the point ${tex`t=${q}`}, you ask? Visually, it is the order defined by the values at ${tex`t=${q}`}, and if they are equal there, compare the values *to the immediate right of* ${tex`${q}`}. Algebraically, we may shift the functions to ${tex`t=${q}`} (substituting ${tex`t-${q}`} in place of ${tex`t`}), and extend the order on ${tex`\mathbb Q`} by stipulating ${tex`t>0`} and ${tex`t0) return 1 if (num_loc*den_loc<0) return -1 } } }33:T4b7,polynomial = { // as an array of coefficients, in increasing powers const evaluate = (p, x)=> { let r=p[0], xi=1 for (let i=1; i { let bc=[1, 1] // binomial coefficients for (let i=1; i=0; j--) { p[j]+=p[i]*bc[j]*xj xj*=-x bc[j+1]+=bc[j] } } return p } const add = (p, q)=> { if (p.length<=q.length) { let r=q.slice(0) for (let i=0; i { let r = Array(p.length+q.length-1).fill(0) for (let i=0; i { let i=0 while (i { return p[lowest_order(p)] } return {evaluate, shift, mult, add, lowest_order, lowest_order_coefficient} }34:[] 2e:{"title":"Computable numbers","cells":[{"id":0,"value":"md`# Computable numbers`","pinned":false,"hidden":false,"mode":"ojs"},{"id":158,"value":"e=\"\\\\epsilon\" // or \"\\\\varepsilon\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"computable_number(e).definition","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"computable_number = function(e=\"\\\\varepsilon\"){\n const def = md`\n**Definition** (Turing): A **computable number** is a (finite, terminating) algorithm \n${tex.block`\n\\begin{aligned}\nx: \\mathbb Q^+ &\\to\\mathbb Q\\times\\mathbb Q \\\\\n${e} \\,\\;\\; &\\mapsto \\; a_{${e}}\\;\\;\\;\\, b_{${e}}\n\\end{aligned}\n`}\nthat satisfies\n>- ${tex`0\\leq b_{${e}}-a_{${e}} \\leq ${e}`} for all ${tex`${e}`}\n>- ${tex`a_{${e}} \\leq a_{${e}'}`} and ${tex`b_{${e}'}\\leq b_{${e}}`} for any ${tex`${e}'<${e}`}\n` \n return new Definition(\"computable number\", def)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"md`Intuitively, the algorithm computes the \"number\" up to a given precision ${tex`${e}`}, and returns an interval instead of a single number; and as ${tex`${e}\\to 0`}, the two bounds are \"squeezing in\". Any rational number ${tex`q\\in\\mathbb Q`} gives a trivial algorithm that always returns ${tex`a_{${e}}=b_{${e}}=q`}. Rather than saying that a computable number is a real number for which such an algorithm exists (after Turing), we *define* the number *as* the algorithm, with no reference to the reals. \n\nIn fact, it's enough to consider ${tex`${e}\\in\\{\\frac{1}{n}\\}\\subset\\mathbb Q^+`} — or an infinite subset thereof, e.g. ${tex`\\{\\frac{1}{10^n}\\}`} — so that the algorithm is tantamount to two monotone sequences converging to the \"number\" from above and below. The general version may come handy for certain algorithms.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":594,"value":"md`Different algorithms may in fact compute the same \"number\", so we'd need a way to identify (i.e., define an equivalence relation on) computable numbers. But first let's get to some interesting examples. We will strive for simplicity of the algorithm, not necessarily to be the shortest per se, and certainly not the most efficient. For sake of readability to get the basic idea across, we shall just use JavaScript's datatype \\`\\`number\\`\\` (which handles both \\`\\`int\\`\\` and \\`\\`float\\`\\`) instead of creating a \\`\\`class\\`\\` for rational numbers as ordered pairs of integers, and define field operations (${tex`+, -, \\times, \\div`}) and order relation ${tex`\\leq`} on them.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"md`## Examples`","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"sqrt2 = function(e) {\n // for each precision e, we want to estimate sqrt2\n // by applying the \"secant method\" on the function x^2-2\n if (e<0) return undefined\n let p=1, q=2\n while (q-p>e) {\n p=(2*p+2)/(p+2)\n q=(2*q+2)/(q+2)\n }\n return [p, q]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":26,"value":"sqrt2(1/10000)","pinned":true,"hidden":false,"mode":"ojs"},{"id":75,"value":"pi = function(e) {\n // Leibniz's formula for pi\n // i.e., Taylor series of arctan\n if (e<1e-8) return undefined\n e/=4\n let p=1, q=1-1/3, n=3\n while (1/n>e) {\n p=q+1/(n+2)\n q=p-1/(n+4)\n n+=4\n }\n return [q*4, p*4]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":179,"value":"pi(1/10000000)","pinned":true,"hidden":false,"mode":"ojs"},{"id":204,"value":"ln2 = function(e) {\n // as integral of 1/x from 1 to 2\n if (e<1e-7) return undefined\n let lower=1/2, upper=1, n=2\n while (upper-lower>e) {\n for (let i=1; i *This is not, by any means, established theory (to my limited knowledge), so I'll revert to using the pronoun *I/me* instead of *we/us* when appropriate.*\n\nBy computable function, I do *not* mean the algorithm that defines a computable number, nor certain functions of the type ${tex`\\mathbb N \\to \\mathbb N`}, but rather functions in the traditional sense: things like ${tex`\\exp`}, ${tex`\\sin`}, elliptic functions, etc., anything that one \"constructs\" using ${tex`+,-,\\times,\\div`}, composition, inverse, integration, and limit operations.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":493,"value":"md`A standard notation: ${tex`\\mathbb Q(t)`} denotes the field of rational functions of one variable with coefficients in ${tex`\\mathbb Q`}; it is to ${tex`\\mathbb Q[t]`} (the ring of polynomials) what ${tex`\\mathbb Q`} is to ${tex`\\mathbb Z`}. Note that each specific rational function is *finitary* (a finite amount of data).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":575,"value":"q = \"q\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":234,"value":"computable_function(q, e).definition","pinned":false,"hidden":false,"mode":"ojs"},{"id":232,"value":"computable_function = function(q=\"q\", e=\"\\\\varepsilon\"){\n const def = md`\n**Definition**: A **computable function** is a (finite, terminating) algorithm \n${tex.block`\n\\begin{aligned}\nf: \\mathbb Q \\times \\mathbb Q^+ &\\to\\mathbb Q(t)\\times\\mathbb Q(t) \\\\\n ${q}\\quad\\; ${e} \\;\\;\\; &\\mapsto \\;\\,a_{${q},${e}}\\quad\\;\\; b_{${q},${e}}\n\\end{aligned}\n`}\n— with the possibility that it may return \\`\\`undefined\\`\\` for some ${tex`${q}`} — that satisfies for each fixed ${tex`${q}`},\n>- ${tex`0\\leq b_{${q},${e}}-a_{${q},${e}} \\leq ${e}`} for all ${tex`${e}>0`} \n>- ${tex`a_{${q},${e}} \\leq a_{${q},${e}'}`} and ${tex`b_{${q},${e}'}\\leq b_{${q},${e}}`} for any ${tex`${e}'<${e}`}\n\nwhere ${tex`\\leq`} denote the order on ${tex`\\mathbb Q(t)`} at the point ${tex`t=${q}`}.\n` \n return new Definition(\"real numbers\", def)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":398,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":450,"value":"md`## Examples \n\nLet's consider the exponential function. The standard definition is by way of its Taylor series\n${tex.block`f(t)=1+t+\\frac{t^2}{2!}+\\frac{t^3}{3!}+\\cdots`}\nFor ${tex`${q}<0`}, ${tex`f(${q})`} is an alternating series, so the upper and lower bounds can be taken to be consecutive partial sums, though it may seem easier — to us, that is — to use ${tex`1/t^{2n}`} and ${tex`0`} instead. For ${tex`${q}>0`}, we need to estimate the remainder. One way is to make use of geometric series\n${tex.block`\n\\begin{aligned}\nf(t) &\\leq 1+t+\\cdots+\\frac{t^n}{n!}+\\frac{t^n}{n!}\\frac{t}{n}+\\frac{t^n}{n!}\\frac{t^2}{n^2}+\\cdots \\\\\n&=1+t+\\cdots+\\frac{t^n}{n!}\\frac{1}{1-\\frac{t}{n}}\n\\end{aligned}`}\nfor ${tex`te) {\n upper.num.push(1/n_fact, 1/(n_fact*(n+1)))\n lower.num.push(1/(n_fact*(n+1)), 1/(n_fact*(n+1)*(n+2)))\n qn*=-q\n n_fact*=(n+1)*(n+2)\n n+=2\n }\n return [lower, upper]\n }\n else {\n let lower=new QQt(1), error=new QQt(0)\n let n=1, n_fact=1, qn=q\n while (n<=q || qn/n_fact*q/(n-q)>e) {\n lower.num.push(1/n_fact)\n error.num.push(0)\n n++\n n_fact*=n\n qn*=q\n }\n lower.num.push(1/n_fact)\n error.num.push(1/n_fact)\n let upper=lower.add(error.div([1, -1/n]))\n return [lower, upper]\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":905,"value":"{\n let x=1, e1=exp(x, 0.01)\n // return e1\n return [e1[0].eval(x), Math.E, e1[1].eval(x)]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1009,"value":"md`Quite some work involved for a simple power series, it turns out. (As this approach favors alternating series, ${tex`\\sin`} and ${tex`\\cos`} would be \"easier\".) There are two other constructions of the exponential function that can claim to be equally natural: 2) as the inverse to ${tex`\\log(x)=\\int_1^x \\frac{dt}{t}`}, and 3) as ${tex`\\lim_{n\\to\\infty}(1+\\frac{x}{n})^n`}.\n\nAs a proof of concept, the notion of computable functions now covers power series (with \"computable coefficients\"), the inverse function of a computable function, primitive (antiderivative) of a computable function, and the \"uniform\" limit of a sequence of computable functions.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1022,"value":"md`A few more items are in order:\n\n- This easily gives a (classical) function from (a subset of) ${tex`\\mathbb Q`} to the set of computable numbers.\n- Extend (the domain) to computable numbers, provided that it's *continuous* there. Note that we have to accept rational functions as continuous.\n- Define equality of computable functions.\n- Construct \"black-box\" operations on computable functions that \"respect\" this equality.\n- Define derivative of a computable function.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1025,"value":"md`What's more exciting is that it may give us a way to define distributions (aka generalized functions) of Laurent Schwartz in this framework. The most important distribution is, without question, the Dirac delta function ${tex`\\delta(t)`}. One intuitive way to think about ${tex`\\delta(t)`} is as the \"limit\" of certain sequences of functions, but we have to be careful to make it comply with our definition. This looks like a pretty good choice:\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1033,"value":"delta = function(q, e) {\n if (q==0 || e<=0) \n return undefined\n else\n return [new QQt(q*e, [0, 1]), new QQt(0)] // i.e., qe/t\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1167,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1165,"value":"delta1 = function(q, e) {\n if (q==0 || e<=0) \n return undefined\n if (q<0)\n return [new QQt(-q*e, [0, 0, 1]), new QQt(0)] // i.e., -qe/t^2\n if (q>0)\n return [new QQt(0), new QQt(-q*e, [0, 0, 1])]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1359,"value":"md`If we are to discretize these distributions supported at ${tex`\\{0\\}`} by \"sampling\" the values at ${tex`${q}=\\pm d`} for a small value of ${tex`d`}, we'd turn it into a discrete function, i.e. an array:\n${tex.block`\n\\begin{aligned}\n\\delta(t) &\\to [\\frac{1}{2}, \\frac{1}{2}] \\\\\n\\delta'(t) &\\to [\\frac{1}{2d}, -\\frac{1}{2d}]\n\\end{aligned}`}\n(in more details: set the precision ${tex`${e}=1`} and take the average of the upper and lower bounds), i.e., when convolved with an arbitrary ${tex`f(t)`},\n${tex.block`\n\\begin{aligned}\n(\\delta * f)(t) &\\to \\frac{f(t+d)+f(t-d)}{2} \\\\\n(\\delta' * f)(t) &\\to \\frac{f(t+d)-f(t-d)}{2d}\n\\end{aligned}`}\nNot bad! Now try ${tex`\\delta''(t)`},\n${tex.block`\\delta''(t) \\to [1,1]/d^2`}\nbut what we really want is\n${tex.block`\\delta''(t) \\to [1,-2,1]/d^2`}\nWell, we can add the middle coefficient in order to make it zero-sum. Can we compute the so-called [finite difference coefficients](http://web.media.mit.edu/~crtaylor/calculator.html) this way?\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1194,"value":"md`## Appendix: code for ${tex`\\mathbb Q(t)`}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":620,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":768,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"import {Proposition, Definition} from \"@neobourbaki/tools\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}