Questions tagged [real-numbers]

The tag has no usage guidance.

47 questions
Filter by
Sorted by
Tagged with
135 views

Why are complex numbers needed to define qubits?

I have started learning about quantum computing, and I have been told that you can forget about the physics and think of qubits as a natural generalization of the notion of bit. According to this view,...
5k views

How can a computer deal with real numbers

Computers are an exceptionally powerful tool for various computations, but they don't excel at storing decimal numbers. However, people have managed to overcome these issues: not storing the number in ...
49 views

What is the computational class of a pushdown automaton with real values?

Say there is a push-down automata, in this example I'll use a deadfish-like set: +: increase x by 1 0: set x to 0 ...
137 views

What are the differences between the set of Real Numbers and the Java datatype float?

Besides the fact that the real numbers ℝ go on forever whereas the floats only go up to a certain point (Float.MAX_VALUE) in Java, what else could I compare between these two sets of numbers?
101 views

What's wrong with this "proof" that $\mathbb{R}$ is enumerable?

The fake proof: We know that $\mathbb{R}$ is uncountable, hence we cannot enumerate over it. But what we do know is that $\mathbb{Q}$, the set of rationals, is countable, and even denumerable. We ...
49 views

Complexity of approximating a function value using queries

I am looking for information on problems of the following kind. There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
93 views

Doubt regarding Cantor's diagonalization argument [closed]

So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider. I understand the overall argument but have a problem regarding one caveat mentioned in my ...
308 views

Is the calculation of infinite sums solvable by a computer?

The question is: I give the computer a sum, such as $\sum_{n=1}^\infty\frac{1}{n^3}$, the computer is expected to return an elegant closed-form solution, because the answer may be irrational. Has this ...
109 views

How can I develop a pseudo-polynomial time algorithm for a non-integer problem?

I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5, \exists j \in J$. Since the problem ...
317 views

Finding a path with a smallest product

Let $G$ be a graph whose edges have integer weights between 1 and 255. What is an efficient algorithm for finding a path between two vertices $s,t$, such that the product of weights on the path is ...
75 views

Is it a bad idea to require a correctness proof as part of a computable real number?

At 30:42 of Norman Wildberger's Difficulties with real numbers as infinite decimals (II) lecture, he raises the question whether "certificates of boundedness" (of the runtime of the algorithm to ...
141 views

Would Schmidhuber's theories of everything be capable of performing hypercomputation?

Jürgen Schmidhuber pointed out that a simple explanation of the universe would be a Turing machine analogy programmed to execute all possible programs computing all possible histories for all types of ...
304 views

Can generalized Turing machines compute all reals?

Super-recursive algorithms are theoretical super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines. In this entry it ...
74 views

Real RAM computational mode

Given a real value $M>0$, I want to compute the greatest value of $\epsilon$ strictly smaller than $M$. Given the assumption that the computational model is Real-RAM, how to find a real number ...
39 views

Semidecidable properties of computable reals

By computable real I mean $x\in\mathbb{R}$ such that there is some computable total function $p_x$ that takes a natural number $n$ and returns a dyadic rational $r$ such that $|x-r|<2^{-n}$. I ...
131 views

How to represent symbolic knowledge using real numbers - theory about neural networks and natural/analog computing?

One can define the semantics of one definite word using the references to real world entities, relationships with the other words and other concepts and represent all this knowledge about this one ...
1k views

Do "Type-2" Turing machines with infinite length inputs have more computational power?

Certain idealizations of a Turing machine yield an increase in computational power, such as an inductive Turing machine, which can (trivially) solve the halting problem if it has an infinite amount of ...
2k views

How does conversion from fixed-point to floating-point happen?

I came across to the code that convert 32-bit signed fixed-point number (16.16) to a float and it looks like (pseudocode) floating = fixed / 65536.0 Could you ...
405 views

Decidable properties of computable reals

Is "Rice's theorem for the computable reals" -- that is, no nontrivial property of the number represented by a given computable real is decidable -- true? Does this correspond in some direct way to ...
71 views

Real RAMs with "reasonable" operations

There is a large body of literature on RAMs with "reasonable" and "unreasonable" operations, where "unreasonable" operations would yield a machine with too much power to be practically feasible. For ...
35 views

When do you know whether an exponent represents a movement of the decimal point to the left?

I'm learning about floating point numbers and I don't quite understand when one should interpret an exponent as moving the decimal point to the left. By book shows an example of converting -10.5 ...
101 views

Total functional computable real numbers

Is there any computable real number which can not be computed by a higher order primitive recursive algorithm? For computable real number I mean those that can be computed by a Turing machine to any ...
325 views

Are IEEE floating point numbers intervals or point values?

The context is IEEE 754-2008 floating point number systems. The systems defined by the standard comprise, as far as I understand it, a bit-level representation and a set of guarantees on the precision ...
284 views

Why mantissa and exponent are stored differently in a float?

As we know, in IEEE 754 standard, float number's exponent and mantissa are stored differently. While the exponent is stored as an unsigned number, taking advantage of the bias, the mantissa is in sign-...
6k views

Find out duplicate number between 1 to N numbers

I first saw this question on this website where I was trying on Java puzzles. Here is the Question:- ...
77 views

Computational complexity of logistic map

My question is pretty simple and to the point. Is there a known way to efficiently compute logistic maps to within a specified precision? In other words, the input is a value $x$ and integers $d,n$; ...
336 views

Why is there more frequent overflow in normalised Floating Point

I read that overflow is more frequent when we work with normalised mantissas. Why is this? Is it because when we adopt a normalised representation, our range is smaller than in a unnormalised ...
31 views

Is there a good model of computation for real numbers? [duplicate]

/!\ I am not speaking about int or float, my question is about model of computation used to design and describe algorithms. The integer numbers case Many algorithms use integers and their ...
39 views

Extended version of the theory of reals and its decidability

It is well-known due to Tarski that the theory of reals $(\mathbb{R},+,\cdot,<,=)$ is decidable. I was asking my self whether one would lose the decidability by adding all real constants. More ...
35 views

Efficient algorithms for finding the limit of a sub-sequence [closed]

Given a sequence $A_N={a_1,a_2,a_3...,a_N}$ of real numbers, and given that there exist some sub-sequence which generated from some deterministic converging sequence. Are there any efficient ...
478 views

Can a probabilistic Turing Machine compute an uncomputable number?

Can a probabilistic Turing Machine compute an uncomputable number? My question probably does not make sense, but, that being the case, is there a reasonably simple formal explanation for it. I should ...
497 views

Unreachable Real Numbers - Randomness & Computability

I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there ...
180 views

Computability of equality to zero for a simple language

Suppose we have a tree in which leaves are labeled with a set of numbers $L$, and internal nodes with a set of operations $O$. In particular $L$ can be $\mathbb{N}, \mathbb{Z}$ or $\mathbb{Q}$, and ...
2k views

Minimize sum of squared error

I have an array of real numbers, I want to partition them into k sets. In each set, I calculate the sum of squared error. Then, I add up all the sum of squared error for all the set. I want to ...
205 views

Is Newton's Method to compute the zeros of a function an algorithm?

Looking for Newton's method in Wikipedia, I read the following: In numerical analysis, Newton's method (also known as the Newton-Raphson method), named after Isaac Newton and Joseph Raphson, is ...
72 views

Computational complexity for more general problems

When I read computational complexity I encounter problems like 3-SAT, set cover, knapsack. In the first two variables are discrete. In knapsack the weights and values are integer and all three ...
891 views

Are there established complexity classes with real numbers?

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ (with ...
3k views

Represent a real number without loss of precision

Current floating point (ANSI C float, double) allow to represent an approximation of a real number. Is there any way to represent real numbers without errors? Here's an idea I had, which is anything ...
104 views

Can Turing Machines decide on computability? [closed]

Can a Turing Machine decide whether an arbitrary real number is computable or not? Does this even follow from the solution of the Halting problem? If not, who proved it?
155 views

Implement Mathematica's capability of rationalizing machine reals

If I have a variable x bound to a machine precision real in Mathematica, I can use y = FromDigits[RealDigits[x]] then y is ...
86 views

How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\}$

I have a real function $f:\mathbb{{R}}^{d}\mapsto\mathbb{R}$, where $d>1$. The question is how to compute the level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\}$. I am a statistician ...
152 views

Minimal positive difference of a mulitset of real numbers

Motivated by Max-Flow: Detect if a given edge is found in some Min-Cut, I'd like to ask the following questions: Given a multiset of real numbers $B$, how hard is it to compute the minimal positive ...
100 views

Rearrange a sequence of real numbers to satisfy polynomial inequalities

Assume we fix a degree $d$ polynomials $f$ of $k$ variables. (If it helps, let $t$ be the number of terms in $f$). Consider a list of real numbers $a_1,\ldots,a_n$, does there exist a permutation $\pi$...
179 views

Why is solving of diagonal quadratic equations over $\mathbb R$ and $\mathbb C$ in $P$?

Let $\mathbb F\in\{\mathbb R, \mathbb C\}$ the field of real or complex numbers. Then [1, page 22 in the middle] claims that the following equation can easily be solved in deterministic polynomial ...
2k views

Does there exist any work on creating a Real Number/Probability Theory Framework in COQ?

COQ is an interactive theorem prover that uses the calculus of inductive constructions, i.e. it relies heavily on inductive types. Using those, discrete structures like natural numbers, rational ...
Is a function looking for subsequences of digits of $\pi$ computable?
How can it be decidable whether $\pi$ has some sequence of digits? inspired me to ask whether the following innocent-looking variation is computable: f(n) = \begin{cases} 1 & \text{if \(\bar ...