hackslash dot org

Matters Computational (2010) [pdf]

Posted: 2025-03-07 10:06:38

Jürgen Schmidhuber's "Matters Computational" provides a comprehensive overview of computer science, spanning its theoretical foundations and practical applications. It delves into topics like algorithmic information theory, computability, complexity theory, and the history of computation, including discussions of Turing machines and the Church-Turing thesis. The book also explores the nature of intelligence and the possibilities of artificial intelligence, covering areas such as machine learning, neural networks, and evolutionary computation. It emphasizes the importance of self-referential systems and universal problem solvers, reflecting Schmidhuber's own research interests in artificial general intelligence. Ultimately, the book aims to provide a unifying perspective on computation, bridging the gap between theoretical computer science and the practical pursuit of artificial intelligence.

Jürgen Schmidhuber's "Matters Computational (2010)" presents a comprehensive, and at times highly technical, overview of theoretical computer science, with a particular focus on its intersection with artificial intelligence and machine learning, specifically Schmidhuber's own contributions to these fields. The book, structured as a collection of previously published papers and new material, explores fundamental computational principles through the lens of algorithmic information theory, Kolmogorov complexity, and the concept of universal problem solvers.

The narrative begins with an exploration of the theoretical foundations of computation, delving into the nature of computability, Turing machines, and the limits of what can be computed. It emphasizes the importance of universality and self-reference in computation, drawing connections to Gödel's incompleteness theorems and the halting problem. Schmidhuber introduces the speed prior, a concept central to his research, which favors programs that not only solve a given problem but do so efficiently. This leads into a discussion of optimal universal search algorithms, such as Levin Search, and their implications for artificial general intelligence.

A substantial portion of the book is dedicated to algorithmic information theory and its application to inductive inference and learning. Schmidhuber argues that the shortest program capable of generating a given data sequence is the best explanation for that sequence, aligning with Occam's Razor and the principle of Minimum Description Length. This theoretical framework is used to analyze the problem of learning from data, including supervised learning, unsupervised learning, and reinforcement learning. He discusses various algorithms for finding short programs, including variations of Levin Search and methods based on Monte Carlo sampling.

The text also delves into the practical implications of these theoretical concepts, examining the design and implementation of artificial neural networks, recurrent neural networks, and other learning systems. Schmidhuber meticulously details his own contributions to the field, including the development of Long Short-Term Memory (LSTM) networks, a type of recurrent neural network architecture designed to address the vanishing gradient problem, which had previously hampered the training of deep networks. He also discusses other architectures like self-referential neural networks and the concept of Gödel machines, self-improving AI systems inspired by Gödel's incompleteness theorems.

Throughout the book, Schmidhuber emphasizes the importance of formal mathematical frameworks for understanding intelligence and the potential for creating truly intelligent machines. He rigorously analyzes the computational complexity of various learning algorithms and discusses the limitations imposed by finite resources. The text is replete with mathematical formulas, algorithms, and proofs, providing a deep dive into the theoretical underpinnings of the field. He concludes with a forward-looking perspective on the future of artificial intelligence, emphasizing the potential for creating increasingly sophisticated and capable learning systems based on the principles outlined in the book. The overarching theme is a pursuit of general purpose artificial intelligence through a formal, mathematically grounded approach centered on optimal program search and algorithmic information theory.

Summary of Comments ( 11 )
https://news.ycombinator.com/item?id=43288861

HN users discuss the density and breadth of "Matters Computational," praising its unique approach to connecting diverse computational topics. Several commenters highlight the book's treatment of randomness, floating-point arithmetic, and the FFT as particularly insightful. The author's background in physics is noted, contributing to the book's distinct perspective. Some find the book challenging, requiring multiple readings to fully grasp the concepts. The free availability of the PDF is appreciated, and its enduring relevance a decade after publication is also remarked upon. A few commenters express interest in a physical copy, while others suggest potential updates or expansions on certain topics.

The Hacker News post titled "Matters Computational (2010) [pdf]" linking to a PDF of Jörg Fliege's book "Matters Computational" has a moderate number of comments, discussing various aspects of the book and computational mathematics in general.

Several commenters praise the book's comprehensive nature and clarity. One user highlights its value as a reference for "all sorts of basic algorithms and data structures," appreciating the detailed explanations and pseudocode provided. They specifically mention its usefulness for understanding fundamental concepts like numerical stability.

Another commenter focuses on the book's treatment of linear algebra, noting its depth and accessibility, even for those without a strong mathematical background. They contrast it with other resources they found less helpful.

A few comments delve into specific topics covered in the book. One user discusses the exploration of floating-point arithmetic and its associated challenges, acknowledging the importance of understanding these concepts for anyone working with numerical computations. Another highlights the chapter on optimization, mentioning its practical value and the inclusion of various optimization algorithms.

Some commenters offer broader perspectives on computational mathematics and its role in computer science. One reflects on the importance of a strong mathematical foundation for software engineers, advocating for more emphasis on these concepts in education.

The discussion also touches on the book's availability. The author's decision to make it freely available is commended, with some users expressing gratitude for open access to such valuable educational resources. A link to the author's webpage is shared, offering further context.

While a number of commenters express interest in the book based on the description and other comments, there isn't extensive engagement in deep technical discussions. The overall sentiment is positive, with the comments primarily focusing on the book's breadth, clarity, and value as a resource for understanding fundamental computational concepts.

A brief meditation on formal systems and lying goblins

permalink

Posted: 2025-03-06 22:00:38

The blog post explores the limitations of formal systems, particularly in discerning truth. It uses the analogy of two goblins, one always truthful and one always lying, to demonstrate how relying solely on a system's rules, without external context or verification, can lead to accepting falsehoods as truths. Even with additional rules added to account for the goblins' lying, clever manipulation can still exploit the system. The post concludes that formal systems, while valuable for structuring thought, are ultimately insufficient for determining truth without external validation or a connection to reality. This highlights the need for critical thinking and skepticism even when dealing with seemingly rigorous systems.

This blog post, titled "A Brief Meditation on Formal Systems and Lying Goblins," delves into the fascinating intersection of formal systems, logic, and the challenges of extracting truthful information from unreliable sources. The author constructs a thought experiment involving a population of goblins, some of whom invariably speak the truth, and others who consistently lie. The central problem revolves around devising a strategy to reliably determine the veracity of statements made by these goblins, given that one cannot ascertain a priori which type of goblin one is interacting with.

The author meticulously lays out the formal framework for this puzzle. They introduce the concept of truth-telling goblins, represented symbolically, and lying goblins, similarly represented. This symbolic representation allows for the manipulation of statements and the exploration of logical consequences within a clearly defined system. The post then proceeds to examine the complexities introduced by the goblins' deceptive nature. A simple question, such as inquiring about the nature of the goblin itself (truth-teller or liar), proves insufficient, as both types would provide the same answer if attempting to deceive.

The core of the post focuses on the development of a questioning strategy that can circumvent the goblins' inherent deceptiveness. The author explores the idea of nested questions, effectively asking a goblin about what another goblin would say. This indirect approach leverages the predictable nature of the goblins' lies: a liar will always lie about what a truth-teller would say, and vice-versa. By carefully constructing these nested inquiries, one can effectively force the goblins to reveal the truth, irrespective of their individual predilection for truth or falsehood.

The author further elaborates on the underlying principles at play, highlighting the power of formal systems in dissecting and solving such puzzles. By representing the problem within a formal framework, one can systematically explore potential solutions and rigorously test their validity. The post concludes by emphasizing the broader implications of this thought experiment. It serves as a microcosm of the challenges we face in the real world when dealing with information from potentially unreliable sources. The ability to construct robust questioning strategies, analogous to the nested inquiries used with the goblins, becomes crucial for navigating a world awash in misinformation and discerning truth from falsehood. The seemingly simple puzzle of the lying goblins thus provides a valuable lesson in the application of formal systems to complex problems of knowledge and belief.

Summary of Comments ( 0 )
https://news.ycombinator.com/item?id=43285485

The Hacker News comments generally praise the clarity and engaging presentation of the article's topic (formal systems and the halting problem, illustrated by a lying goblin puzzle). Several commenters discuss the philosophical implications of the piece, particularly regarding the nature of truth and provability within defined systems. Some draw parallels to Gödel's incompleteness theorems, while others offer alternate goblin scenarios or slight modifications to the puzzle's rules. A few commenters suggest related resources, such as Raymond Smullyan's work, which explores similar logical puzzles. There's also a short thread discussing the potential applicability of these concepts to legal systems and contract interpretation.

The Hacker News post "A brief meditation on formal systems and lying goblins" has generated several comments discussing the article's premise and exploring related concepts.

Several commenters engage with the core idea of the article, which uses the analogy of lying goblins to illustrate how seemingly sound logical systems can lead to incorrect conclusions if based on false premises. One commenter points out the parallel to real-world scenarios where misinformation or flawed assumptions can corrupt a system, regardless of its internal consistency. They mention how this applies to areas like political discourse and conspiracy theories.

Another commenter delves deeper into the concept of formal systems, emphasizing the distinction between validity and soundness. They clarify that a valid argument can still be untrue if its premises are false, echoing the goblin analogy. They also introduce the idea of Gödel's incompleteness theorems, suggesting that even consistent formal systems can contain unprovable truths.

The discussion extends to the practical implications of these ideas. One commenter reflects on the challenge of identifying false premises in real-world situations, highlighting the importance of critical thinking and questioning assumptions. Another commenter draws a connection to Bayesian reasoning, suggesting that incorporating prior probabilities can help mitigate the risk of being misled by false information.

Further comments explore related philosophical themes, touching on the nature of truth and the limits of knowledge. One commenter mentions the concept of "unknown unknowns," emphasizing the difficulty of accounting for information that we are not even aware of.

Some commenters also offer alternative analogies to illustrate the same principles. One suggests the image of a perfectly functioning calculator that produces incorrect results due to a user inputting the wrong numbers.

Overall, the comments on the Hacker News post provide a thoughtful and engaging discussion of the article's core ideas, exploring their implications in various contexts and connecting them to broader philosophical and mathematical concepts. They highlight the importance of critical thinking, the limitations of formal systems, and the challenges of navigating a world filled with potentially misleading information.

New Proofs Probe the Limits of Mathematical Truth

permalink

Posted: 2025-02-03 17:34:17

Mathematicians are exploring the boundaries of provability using large language models (LLMs) and other automated theorem provers. While these tools can generate novel and valid proofs, they often rely on techniques too complex for human comprehension. This raises questions about the nature of mathematical truth and understanding. If a proof is too long or intricate for any human to verify, does it truly constitute "knowledge"? Researchers are investigating ways to make these computer-generated proofs more accessible and understandable, potentially revealing new insights into mathematical structures along the way. The ultimate goal is to find a balance between the power of automated proving and the human need for comprehensible explanations.

Within the intricate realm of mathematical logic, a recent surge of groundbreaking proofs has ignited a profound reevaluation of the very nature of mathematical truth and the inherent limitations of our capacity to attain it. These novel demonstrations, explored in depth in "New Proofs Probe the Limits of Mathematical Truth," delve into the profound implications of Gödel's incompleteness theorems, revealing a landscape where certain mathematical truths remain perpetually beyond the grasp of formal proof systems. Specifically, the article focuses on the limitations imposed by these theorems on our ability to resolve fundamental questions within set theory, the bedrock upon which much of modern mathematics is constructed.

The article elucidates the nuanced interplay between different axiomatic systems, emphasizing that the truth of a mathematical statement is intrinsically linked to the specific axioms one chooses to embrace. It explicates how certain statements, while potentially true within the framework of one set of axioms, might remain undecidable or even demonstrably false under a different axiomatic framework. This inherent relativity of mathematical truth, though unsettling to some, underscores the profound richness and complexity of the mathematical universe.

The recent proofs discussed in the article highlight the existence of mathematical statements that are independent of the standard axioms of set theory, commonly known as ZFC (Zermelo-Fraenkel with the Axiom of Choice). This independence signifies that these statements can neither be proven nor disproven using ZFC, thereby revealing fundamental limitations in our ability to fully characterize the mathematical landscape using this particular axiomatic system. The article details specific examples of such independent statements, illuminating the intricate arguments employed to establish their independence and the broader implications these findings have for our understanding of mathematical truth.

The article further explores the concept of forcing, a sophisticated technique developed by Paul Cohen, which allows mathematicians to construct alternative models of set theory. By meticulously manipulating the properties of these models, mathematicians can demonstrate the independence of certain statements from ZFC, thereby showcasing the power and utility of this intricate method. The article provides an accessible explanation of the underlying principles of forcing, enabling readers to appreciate the profound impact this technique has had on the field of mathematical logic.

Finally, the article touches upon the philosophical implications of these recent advancements, prompting a reevaluation of the very foundations of mathematical knowledge. It raises profound questions about the nature of mathematical truth, the role of axioms in shaping our understanding of mathematics, and the ultimate limits of our ability to unravel the intricate tapestry of mathematical reality. It suggests that the pursuit of mathematical truth is an ongoing journey, one characterized by the continual exploration of new axiomatic systems and the persistent probing of the boundaries of what can be known. This ongoing quest, driven by the inherent human desire to understand the fundamental principles governing the mathematical universe, promises to yield further insights into the intricate nature of mathematical truth and the profound limitations that shape our pursuit of it.

Summary of Comments ( 3 )
https://news.ycombinator.com/item?id=42920657

HN commenters discuss the implications of Gödel's incompleteness theorems and the article's exploration of concrete examples in Ramsey theory and Diophantine equations. Some debate the philosophical significance of undecidable statements, questioning whether they represent "true" mathematical facts or merely artifacts of formal systems. Others highlight the practical limitations of proof assistants and the ongoing search for more powerful automated theorem provers. The connection between computability and the physical universe is also raised, with some suggesting that undecidable statements could have physical implications, while others argue for a separation between abstract mathematics and the concrete world. Several commenters express appreciation for the article's clarity in explaining complex mathematical concepts to a lay audience.

The Hacker News post titled "New Proofs Probe the Limits of Mathematical Truth," linking to a Quanta Magazine article, has generated a moderate discussion with several interesting comments exploring different facets of the topic.

Several commenters engage with the concept of "consistency strength," a key theme in the article. One commenter explains it in layman's terms as a hierarchy of axioms, where stronger axioms can prove more theorems but also carry a greater risk of inconsistency. Another clarifies the distinction between consistency and soundness, highlighting that a system can be consistent without being sound, meaning it can be free of contradictions but still not reflect true statements about the world. A further comment connects this to Gödel's incompleteness theorems, explaining how they demonstrate the inherent limitations of formal systems in proving all true statements within their framework.

A recurring point of discussion is the practical implications of these abstract mathematical concepts. Some commenters question the real-world relevance of exploring such esoteric areas of mathematics. Others argue that these explorations are crucial for the foundations of mathematics and computer science, potentially leading to breakthroughs in areas like cryptography and theoretical computer science. One commenter draws an analogy to physics, suggesting that seemingly abstract theoretical research can eventually have profound practical applications, just as quantum mechanics, once a purely theoretical pursuit, now underpins many modern technologies.

Another thread of conversation delves into the philosophical implications of the article's themes. One commenter contemplates the nature of mathematical truth itself, questioning whether it's discovered or invented. Another discusses the concept of "universes" of mathematics, with different sets of axioms leading to different possible mathematical realities. This leads to a discussion about the nature of infinity and different sizes of infinity, referencing Cantor's work on set theory.

Finally, some comments provide additional context and resources related to the article. One commenter mentions the role of large cardinal axioms in set theory and their connection to consistency strength. Another points out the work of Harvey Friedman on concrete incompleteness results, suggesting further reading for those interested in exploring the topic in more depth.

Anatomy of a Formal Proof

permalink

Posted: 2025-01-24 18:19:35

This article dissects the structure of a formal mathematical proof, illustrating it with a simple example about even and odd numbers. It emphasizes the distinction between informal proofs aimed at human understanding and formal proofs designed for automated verification. Formal proofs meticulously lay out every logical step, referencing specific axioms and inference rules within a chosen formal system. This detailed approach, while tedious for humans, enables computer-assisted verification and eliminates ambiguity, ensuring absolute rigor. The article highlights the importance of choosing appropriate axioms and the role of proof assistants in constructing and checking these complex formal structures, ultimately increasing confidence in mathematical results.

The American Mathematical Society's Notices article, "Anatomy of a Formal Proof," delves into the intricate process of constructing a formal mathematical proof, contrasting it with the more informal proofs typically encountered in mathematical publications. It emphasizes that formal proofs, unlike their informal counterparts, are meticulously detailed and rigorously structured to be verifiable by automated proof assistants, also known as proof checkers. These software tools require a level of precision far exceeding human expectations in traditional mathematical discourse.

The article elucidates this distinction by dissecting a specific example: the formalization of a theorem concerning Cauchy sequences in metric spaces. This theorem, relatively simple in its informal presentation, becomes considerably more complex when formalized. The formalization process necessitates explicitly stating and proving many foundational concepts that are often implicitly assumed in informal proofs. This includes defining fundamental notions like equality, ordered pairs, functions, Cartesian products, and the real numbers, all within the specific logical framework of the proof assistant. The article highlights the substantial effort required to build this foundational layer, illustrating the "iceberg phenomenon" where a concise informal proof rests upon a vast, submerged body of underlying definitions and lemmas.

Furthermore, the article explores the challenges of translating informal mathematical language, rich with nuances and implicit understandings, into the rigid and unambiguous syntax demanded by formal proof systems. This translation process requires a meticulous deconstruction of the informal argument, meticulously filling in all the implicit steps and justifications. The article underscores that this often reveals hidden complexities and ambiguities in the informal proof, forcing mathematicians to confront subtle assumptions they might have unconsciously made.

The authors describe the iterative nature of formal proof development. The process typically involves writing a formal proof sketch, attempting to verify it with the proof assistant, addressing the resulting errors and gaps, and repeating this cycle until the entire proof is formally verified. This iterative refinement, aided by the precise feedback from the proof assistant, contributes to an exceptionally high level of certainty in the correctness of the final formalized proof.

The article concludes by reflecting on the broader implications of formalization for mathematical practice. While acknowledging the significant investment of time and effort required, it highlights the benefits of increased confidence in the validity of complex mathematical arguments, the potential for discovering new mathematical insights through the formalization process, and the role formalization plays in bridging the gap between human mathematical reasoning and computational verification. The authors suggest that while full formalization of all mathematical results is likely impractical, strategically formalizing key theorems and foundational concepts can significantly enhance the rigor and reliability of mathematics as a whole.

Summary of Comments ( 0 )
https://news.ycombinator.com/item?id=42815755

HN commenters discuss the accessibility of formal proof systems, particularly referencing Lean. Some express excitement about the potential of formal proofs to revolutionize mathematics, while others are more skeptical, citing the steep learning curve and questioning the practical benefits for most mathematicians. Several commenters debate the role of intuition versus rigor in mathematical practice, with some arguing that formalization can enhance understanding and others suggesting it might stifle creativity. The feasibility of formalizing existing mathematical knowledge is also discussed, with varying opinions on the timescale and resources required for such a project. Some users highlight the potential of AI in assisting with formalization efforts, while others remain cautious about its current capabilities. The overall tone is one of cautious optimism, acknowledging the challenges but also recognizing the potential transformative power of formal proof systems.

The Hacker News post "Anatomy of a Formal Proof" (linking to an American Mathematical Society article detailing a formal proof of the Central Limit Theorem) generated a moderate discussion with several interesting points.

A few commenters discussed the practical implications and applications of formal proofs. One noted the potential for increased trust in critical systems, suggesting that formal proofs could eliminate bugs and vulnerabilities in areas like flight control software. They highlighted the importance of this, given the increasing complexity and reliance on software in critical systems. Another commenter pondered the future impact on mathematics education, speculating that tools and techniques from formal proof systems might eventually filter down to the undergraduate or even high school level, changing how math is taught.

The conversation also touched upon the evolution and accessibility of formal proof tools. One commenter, familiar with older systems like Mizar, expressed pleasant surprise at the relative readability and clarity of the Isabelle/HOL proof presented in the article. They viewed this as a significant advancement in making formal methods more approachable. Another commenter pointed out the existing applications of formal methods in hardware verification, suggesting that the software world could learn from the hardware industry's experience.

Some comments delved into the philosophical implications of formal proofs. One commenter questioned the ultimate value of formalization, arguing that informal proofs, while potentially flawed, still hold significant value due to their accessibility and explanatory power. They suggested that the effort involved in formalization might outweigh the benefits in some cases. This sparked a counter-argument emphasizing that informal proofs can hide subtle errors, and the rigor of formalization provides a higher level of certainty, even if it comes at a cost in terms of complexity.

Finally, several comments focused on the specific tools and techniques used in the proof. Commenters mentioned specific proof assistants like Lean, Coq, and Isabelle/HOL, comparing their features and discussing their respective communities. There was also some discussion of the trade-offs between different approaches to formalization, with some commenters expressing preferences for particular styles or methods.

In summary, the comments on the Hacker News post explored the practical, pedagogical, philosophical, and technical aspects of formal proofs, reflecting the diverse interests of the Hacker News community. The discussion provided a nuanced perspective on the potential benefits and challenges of formalization in mathematics and beyond.

Stories with Tag formal systems

Matters Computational (2010) [pdf]

Summary of Comments ( 11 ) https://news.ycombinator.com/item?id=43288861

A brief meditation on formal systems and lying goblins

Summary of Comments ( 0 ) https://news.ycombinator.com/item?id=43285485

New Proofs Probe the Limits of Mathematical Truth

Summary of Comments ( 3 ) https://news.ycombinator.com/item?id=42920657

Anatomy of a Formal Proof

Summary of Comments ( 0 ) https://news.ycombinator.com/item?id=42815755

Summary of Comments ( 11 )
https://news.ycombinator.com/item?id=43288861

Summary of Comments ( 0 )
https://news.ycombinator.com/item?id=43285485

Summary of Comments ( 3 )
https://news.ycombinator.com/item?id=42920657

Summary of Comments ( 0 )
https://news.ycombinator.com/item?id=42815755