People who code: we want your input. Take the Survey
37

Sage is an open source computer algebra system. Let's see if it can handle your basic example: sage: sqrt(3) * (4/sqrt(3) - sqrt(3)) 1 What is happening under the hood? Sage is storing everything as a symbolic expression, which it is able to manipulate and simplify using some basic rules. Here is another example: sage: 1 + exp(pi*i) 0 So sage can also ...


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

Computer algebra is a huge area, probably at least a semester-long university-level course to get most of the basics. However, I think we can cover some of the flavour of it here. Your case is the easy case, because it is entirely within the language of algebraic numbers (i.e. roots of polynomials), and manipulating polynomials is really the foundation of ...


9

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 ...


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 ...


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

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

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

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 ...


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.


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 + \...


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

Consider the following reasonable definition for a Turing machine computing an irrational number in $[0,1]$. A Turing machine computes an irrational $r \in [0,1]$ if, on input $n$, it outputs the first $n$ digits (after the decimal) of the binary representation of $r$. One can think of many extensions of this definition for probabilistic Turing machines. ...


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

You can run any standard quantum algorithm on a real-amplitude quantum computer with one additional qubit and only constant-factor slowdown (or perhaps linear-factor slowdown considering loss of parallelism) by replacing each $a{+}bi$ in your unitary matrices by $\big(\begin{smallmatrix}a&-b\\b&a\end{smallmatrix}\big)$. Likewise, you can simulate a ...


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