Galois theory of algorithms

DOI10.1007/978-3-319-47843-2_17MaRDI QIDQ3299851zbMATH OpenOpenAlexFDO

Authors Noson S. Yanofsky

Publication date 27 July 2020

Published in Outstanding Contributions to Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.0014

zbMATH Keywords

algorithmscomputable functionsGalois theorymonoidal categories

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Monoidal categories, symmetric monoidal categories (18M05) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) General topics in the theory of algorithms (68W01)

Abstract: Many different programs are the implementation of the same algorithm. The collection of programs can be partitioned into different classes corresponding to the algorithms they implement. This makes the collection of algorithms a quotient of the collection of programs. Similarly, there are many different algorithms that implement the same computable function. The collection of algorithms can be partitioned into different classes corresponding to what computable function they implement. This makes the collection of computable functions into a quotient of the collection of algorithms. Algorithms are intermediate between programs and functions: Programs $woheadrightarrow$ Algorithms $woheadrightarrow$ Functions. oindent Galois theory investigates the way that a subobject sits inside an object. We investigate how a quotient object sits inside an object. By looking at the Galois group of programs, we study the intermediate types of algorithms possible and the types of structures these algorithms can have.

Recommendations

• scientific article; zbMATH DE number 53530
• Towards a definition of an algorithm
• Computable fields and Galois theory
• scientific article; zbMATH DE number 1775057
• scientific article; zbMATH DE number 1189004

Cites work

• Cartesian categories with natural numbers object
• Definability and invariance
• scientific article; zbMATH DE number 3944108 (Why is no real title available?)
• scientific article; zbMATH DE number 3677917 (Why is no real title available?)
• scientific article; zbMATH DE number 1216133 (Why is no real title available?)
• scientific article; zbMATH DE number 475238 (Why is no real title available?)
• scientific article; zbMATH DE number 1759230 (Why is no real title available?)
• scientific article; zbMATH DE number 1373518 (Why is no real title available?)
• Lectures on n-categories and cohomology
• Pre-recursive categories
• Towards a definition of an algorithm
• When are Two Algorithms the Same?

Cited in

(5)

• scientific article; zbMATH DE number 4074461 (Why is no real title available?)
• scientific article; zbMATH DE number 1985576 (Why is no real title available?)
• An efficient algorithm for the computation of Galois automorphisms
• From Dyson-Schwinger equations to quantum entanglement
• Subsystems via quantum motions

This page was built for publication: Galois theory of algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3299851)