22

There is no way to represent all real numbers without errors if each number is to have a finite representation. There are uncountably many real numbers but only countably many finite strings of 1's and 0's that you could use to represent them with.


20

It all depends what you want to do. For example, what you show is a great way of representing rational numbers. But it still can't represent something like $\pi$ or $e$ perfectly. In fact, many languages such as Haskell and Scheme have built in support for rational numbers, storing them in the form $\frac{a}{b}$ where $a,b$ are integers. The main reason ...


18

First encode natural numbers and pairs, as described by jmad. Represent an integer $k$ as a pair of natural numbers $(a,b)$ such that $k = a - b$. Then you can define the usual operations on integers as (using Haskell notation for $\lambda$-calculus): neg = \k -> (snd k, fst k) add = \k m -> (fst k + fst m, snd k + snd m) sub = \k m -> add k (neg ...


13

Lambda-calculus can encode most data structures and basic types. For example, you can encode a pair of existing terms in the lambda calculus, using the same Church encoding that you usually see to encode nonnegative integers and boolean: $$\mbox{pair}= λxyz.zxy$$ $$\mbox{fst} = λp.p(λxy.x)$$ $$\mbox{snd} = λp.p(λxy.y)$$ Then the pair $(a,b)$ is $p=(\mbox{...


8

A real number cannot be input into a Turing machine, since it is an infinite object. There are various models for providing a Turing machine with oracle access to real numbers, but these are by definition computable. You could imagine a Turing machine given a ZFC definition of a real number, and in that case it's undecidable. For example, given a Turing ...


8

Yes. There are. There is the real-RAM/BSS model mentioned in the other answer. The model has some issues and AFAIK there is not much research activity about it. Arguably, it is not a realistic model of computation. The more active notion of real computability is that of higher type computation model. The basic idea is that you define complexity for higher ...


8

The model you describe is known as the Blum-Shub-Smale (BSS) model (also Real RAM model) and indeed used to define complexity classes. Some interesting problems in this domain are the classes $P_R$, $NP_R$, and of course the question of whether $P_R$ = $NP_R$. By $P_R$ we mean the problem is polynomially decidable, $NP_R$ is the problem is polynomially ...


8

Yes, Rice's theorem for reals holds in every reasonable version of computable reals. I will first prove a certain theorem and a corollary, and explain what it has to do with computability later. Theorem: Suppose $p : \mathbb{R} \to \{0,1\}$ is a map and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then there exists a Cauchy sequence ...


8

Any machine model in which a machine can be described by a string over a fixed alphabet can only compute countably many things. Since there are uncountably many real numbers, all of these machine models fail to compute almost all real numbers. In fact, the alphabet need not be fixed. It is enough that the alphabet is taken from some countable set of finite ...


7

Your idea does not work because a number represented in base $b$ with mantissa $m$ and exponent $e$ is the rational number $b \cdot m^{-e}$, thus your representation works precisely for rational numbers and no others. You cannot represent $\sqrt{2}$ for instance. There is a whole branch of computable mathematics which deals with exact real arithmetic. Many ...


7

There are many effective Rational Number implementations but one that has been proposed many times and can even handle some irrationals quite well is Continued Fractions. Quote from Continued Fractions by Darren C. Collins: Theorem 5-1. - The continued fraction expression of a real number is finite if and only if the real number is rational. Quote ...


7

The standard library of Coq has a section about real numbers. These are the classical real numbers, using the Dedekind completion. There are also results about complex numbers, I suppose there are several libraries, I happen to know this one. Note that there is also a lot of results for constructive real and complex numbers, C-CoRN is the reference. Side ...


7

Type-2 Turing machines are not more powerful than ordinary Turing machines in the sense that any map $\mathbb{N} \to \mathbb{N}$ that can be computed by a type-2 machine can also be computed by an ordinary machine. To see this, suppose a type-2 Turing machine $T$ computes a function $f : \mathbb{N} \to \mathbb{N}$. We can convert $T$ to an ordinary machine ...


6

Let's assume that the numbers $a_1,\ldots,a_n$ are integers, so that the problem is in NP for any fixed $f$. We construct a polynomial $f$ so that the problem is NP-complete, by reduction from vertex cover in cubic graphs ($3$-regular graphs). Let the instance of cubic vertex cover consist of a cubic graph $G=(V,E)$ and an integer $m$, and let $|V| = n$. ...


6

We assume that we are allowed to take square roots in $\mathbb{F}$. $\mathbb{F} = \mathbb{C}$: If $b = 0$ then $x_1 = \cdots = x_n = 0$ is a solution. If $b \neq 0$ and $a_1 = \cdots = a_n = 0$ then there is no solution. Otherwise, let $a_i \neq 0$, and then a solution is $x_i = \sqrt{b/a_i}$ and $x_j = 0$ for $j \neq i$. $\mathbb{F} = \mathbb{R}$: If $b = ...


6

Here is the question: You are given a list of length $n+1$ which contains the numbers $1,\ldots,n$, one of them appearing twice (and the rest appearing once). Find the number which appears twice. The sum of numbers from $1$ to $n$ is $\frac{n(n+1)}{2}$, so if you subtract that from the sum of the list you get the number appearing twice.


5

There are a number of "exact real" suggestions in the comments (e.g. continued fractions, linear fractional transformations, etc). The typical catch is that while you can compute answers to a formula, equality is often undecidable. However, if you're just interested in algebraic numbers, then you're in luck: The theory of real closed fields is complete, o-...


5

The continued fraction algorithm is easy enough to implement. The first step is to compute the continued fraction of the input $x = [c_0;c_1,\ldots]$. You start with $x_0 = x$, and use the recurrence $c_i = \lfloor x_i \rfloor$, $x_{i+1} = 1/(x_i - c_i)$. You stop when $x_i - c_i$ is "small enough". The next step is to compute the convergent of the continued ...


5

We can compute $$ f(\theta) = -N\log (2\pi)-\frac{1}{2}\sum_{i=1}^N (\langle x_i,\theta \rangle -y_i)^2. $$ Expanding this out, we get that $f(\theta)$ is some quadratic form: $$ f(\theta) = \theta' A \theta + v'\theta + C, $$ where $A$ is symmetric. The next step is to get rid of the linear term. Let $\theta = \psi + \epsilon$. Then $$ \theta' A \theta + \...


5

Turing machines, in the classical sense, decide languages of finite strings over finite alphabets. Your logical language has uncountably many constant symbols so you can't even write down all the formulas as strings, let alone ask a Turing machine to decide things about the collection of formulas.


4

In a nutshell: Printing a random non-computable real is a meaningless task, for precise technical reasons. The meaningful problem is to print non-computable numbers precisely identified by some unique property. But these cannot be printed by any program precisely because they are not computable. Using randomness in the hope of printing by chance the ...


4

If you use the operators $\{+,-,\times,/\}$ (i.e., you don't included the power operator), then all of your problems are likely decidable. Testing equality with zero For instance, let's consider $L = \mathbb{Z} \cup \{\pi\}$. Then you can treat $\pi$ as a formal symbol, so that each leaf is a polynomial in $\mathbb{Z}[\pi]$ (e.g., the integer $5$ is the ...


4

This is a rather tricky question! As you seem to understand, the real issue is the presence of $\hat{}$. It is intimately related to a well known conjecture: Schanuel's conjecture, which states that, essentially, there are no non-trivial algebraic relationships between $\pi$ and $e$. The (expected) positive answer to this conjecture would give you a ...


4

The set of higher-order primitive recursive reals is essentially the class of functions $\mathbb{N}\rightarrow\mathbb{N}$ which can be represented by a term $\mathrm{Nat}\rightarrow\mathrm{Nat}$ in Gödel's system T. Since every such function is total, and every well-typed term in the system can be enumerated effectively, there is a relatively easy proof by ...


4

There are several issues with your question but perhaps I can clarify some issues. First off you assume $f(1) = 1.999...$ and also that no $x \in \mathbb{N}$ exists such that $f(x) = 2$ but that's a contradiction in terms because $1.999... = 2$ and thus $f(1) = 2$. Why does $1.999... = 2$? Well there's an easy answer but not fulfilling answer and a more ...


3

You are looking for an optimal 1-dimensional k-means algorithm. The k-means objective function for partitioning the data $x_1, \ldots, x_n$ into $k$ sets $S = \{S_1, \ldots, S_k\}$. $$ \sum\limits_{i=1}^k \sum\limits_{x \in S_i}\lVert x - \mu_i \rVert^2 $$ where $\mu_i$ is the mean of $S_i$ [1]. You can apply a dynamic programming algorithm to the ...


3

It's pretty clearly an algorithm according to my definition in the linked question. I think your real question is "what is the problem, if any, for which this algorithm is correct?" The answer would be something like "given some stuff and a number of iterations, output a value satisfying some condition with an accuracy related to the iteration count."


3

Original formulation (Originally, the OP was interested in the minimum absolute difference rather than the minimum non-zero absolute difference.) You are asking two different questions. For the first, consider the restricted version in which all numbers are rational, and the decision variant in which the problem is to decide whether your expression is at ...


3

Check this out! http://coq.io/opam/coq-markov.8.5.0.html. A library for Markov's inequality built on mathematical probability theory.


3

Note that $f$ can be the constant $1$ even if $\pi$ is not a normal number. (In French we say if $f$ is constant that $\pi$ is a nombre univers. I don't know the corresponding term in English) For what it's worth: it could be, in the following way: Proving $f$ is computable would not necessarily imply the resolution of the open question whether $f$ is ...


Only top voted, non community-wiki answers of a minimum length are eligible