Concept# Computable number

Summary

In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. They are also known as the recursive numbers, effective numbers or the computable reals or recursive reals. The concept of a computable real number was introduced by Emile Borel in 1912, using the intuitive notion of computability available at the time.
Equivalent definitions can be given using μ-recursive functions, Turing machines, or λ-calculus as the formal representation of algorithms. The computable numbers form a real closed field and can be used in the place of real numbers for many, but not all, mathematical purposes.
Informal definition using a Turing machine as example
In the following, Marvin Minsky defines the numbers to be computed in a manner similar to those defined by Alan Turing in 1936; i.e., as "sequences of digits interpreted as decimal fractions" between 0 and 1:
A computable number [is] one for which there

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people

No results

Related publications (1)

Loading

Related units

No results

The field of computational topology has developed many powerful tools to describe the shape of data, offering an alternative point of view from classical statistics. This results in a variety of complex structures that are not always directly amenable for machine learning tasks. We develop theory and algorithms to produce computable representations of simplicial or cell complexes, potentially equipped with additional information such as signals and multifiltrations. The common goal of the topics discussed in this thesis is to find reduced representations of these often high dimensional and complex structures to better visualize, transform or formulate theoretical results about them. We extend the well known graph learning algorithm node2vec to simplicial complexes, a higher dimensional analogue of graphs. To this end we propose a way to define random walks on simplicial complexes, which we then use to design an extension of node2vec called k-simplex2vec, producing a representation of the simplices in a Euclidean space. Furthermore, the study of this method leads to interesting questions about robustness of graph and simplicial learning methods. In the case of graphs, we study node2vec embeddings arising from different parameter sets, analysing their quality and stability using various measures. In the topic of signal processing, we explore how discrete Morse theory can be used for compression and reconstruction of cell complexes equipped with signals. In particular we study the effect of the compression of a complex on the Hodge decomposition of its signals. We study how the signal changes through compression and reconstruction by introducing a topological reconstruction error, showing in particular that part of the Hodge decomposition is preserved. Moreover, we prove that any deformation retract over R can be expressed as a Morse deformation retract in a well-chosen basis, thus extending the reconstruction results to any deformation retract. In addition, we introduce an algorithm to minimize the loss induced by the reconstruction of a compressed signal. Finally, we use discrete Morse theory to compute an invariant of multi-parameter persistent homology, the rank invariant. We can restrict a multi-parameter persistence module to a one- dimensional persistence module along any line of positive slope and compute the one-dimensional analogue of the rank invariant, namely the barcode. Through a discrete Morse matching we can determine critical values in the multifiltration, which in turn allows us to identify equivalence classes of lines in the parameter space. In our main result, we explain how to compute the barcode along any given line of an equivalence class given the barcode along a representative line. This provides a way to fiber the rank invariant according to the critical values of a discrete Morse matching and to perform computations in the corresponding one-dimensional module, which is much better understood.

Related concepts (27)

Real number

In mathematics, a real number is a number that can be used to measure a continuous one-dimensional quantity such as a distance, duration or temperature. Here, continuous means that pairs of values c

Halting problem

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to r

Pi

The number π (paɪ; spelled out as "pi") is a mathematical constant that is the ratio of a circle's circumference to its diameter, approximately equal to 3.14159. The number π appears in many fo

Related courses (9)

COM-501: Advanced cryptography

This course reviews some failure cases in public-key cryptography. It introduces some cryptanalysis techniques. It also presents fundamentals in cryptography such as interactive proofs. Finally, it presents some techniques to validate the security of cryptographic primitives.

MATH-351: Advanced numerical analysis

The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.

MATH-106(e): Analysis II

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles de plusieurs
variables.

Related lectures (12)