□ 연구개요 Errorless Computing over Continuous Structures in Linear Algebra and Analysis: Since its early days, Computer Science has enjoyed the support and guidance of Logic, from Theory via Engineering to Practice: recall Alan Turing’s 1936 publication preceding nowadays ubiquitous digital computers, or Alonzo Church’s Lambda Calculus having led to functional programming languages, or axiomatic structures in Model Theory corresponding to specification of Abstract Data Types, or Hoare Logic for formal program verification---concerning the processing of discrete data, such as graphs or integers or strings. Continuous data on the other hand commonly arises in Engineering and Science (natura non facit saltus) in the form of temperatures and fields; it mathematically includes real numbers, smooth functions, bounded operators, or compact subsets of an abstract metric space. Processing such continuous data has arguably been lacking the foundation and support from Logic in Computer Science that the discrete case is enjoying [http://ams.org/notices/200603/fea-cook.pdf] The present project has developed these foundations from theory to practice. □ 연구 목표대비 연구결과 “Shoot for the Moon - even if you miss it, you will land among the stars.” (Les Brown). And this project has deliberately aimed for the impossible in order to achieve the incredible: While the Second Numerical Revolution is not complete, we definitely have started it and made major strides that demonstrate its benefits with several proofsof-concept: ● We have developed, analyzed, implemented, and run reliable algorithms in the Exact Real Computation paradigm that compute Periods (i.e. volumes of semi-algebraic sets) ― but it remains to dis/prove open conjectures in Transcendental Number Theory, such as concerning Bloch’s Constant. ● We have determined the intrinsic computational complexity of classical solutions to linear PDEs and the computability of nonlinear Navier-Stokes’ Equation (NSE) ― but it remains to determine the complexity of NSE. ● We have defined and constructed optimal codes of generic compact metric spaces ― but it remains to adapt these to the Hilbert and Sobolev spaces common in analysis. □ 연구개발성과의 활용 계획 및 기대효과(연구개발결과의 중요성) Deviations between mathematical structures and their hardware counterparts are common also in the discrete realm, such as the wraparound 255+1=0 occurring in bytes that led to the “Nuclear Gandhi” programming bug. Therefore nowadays' highlevel programming languages (like Java or Python) provide user data types (like BigInt) that fully agree with mathematical integers, simulated in software using a variable number of hardware bytes; and advanced discrete data types (such as weighted or labeled graphs) can and do build on that, reliably and efficiently. Yet 35 years after introduction and hardware standardization of IEEE 754 floating point numbers, mainstream numerics is still governed by this forcible discretization of continuous data---in spite of violating associative and distributive laws, breaking symmetries, introducing and propagating rounding errors in addition to an involved (and incomplete) axiomatization including NaNs and denormalized numbers. Like “Nuclear Gandhi” in the discrete realm, the discrepancies between continuous mathematical and hardware data types lead to erroneous numerical computations, such as in the maiden flight of Ariane 501 or the design of the Slapner-A oil platform. The lack of a rigorous complexity theory of continuous data leads to a bottomless pit of numerical methods “believed” optimal. The present project has mended most of these deficiencies, and thus has effectively filled the blind spot of traditional computer science with respect to continuous data. (source : 연구결과 요약문 3p)
- 연구책임자 : 마틴 지글러
- 주관연구기관 : 한국과학기술원
- 발행년도 : 20220300
- Keyword : 1. 계산이론;계산복잡도이론;근사알고리즘;전산논리학;재귀적 해석학; 2. Theory of Computation;Computational Complexity;Approximation Algorithm;Logic in Computer Science;Recursive Analysis;
