General Problem Solver: Fundamentals and Applications

By Fouad Sabry

What Is General Problem Solver

GPS, which stands for "General Problem Solver," is a computer program that was developed in 1957 by Herbert A. Simon, J. C. Shaw, and Allen Newell with the intention of functioning as a universal problem solver machine. Analyzing the relationship between means and ends is central to the operation of the GPS, in contrast to the Logic Theorist endeavor.

How You Will Benefit

(I) Insights, and validations about the following topics:

Chapter 1: General Problem Solver

Chapter 2: First-order logic

Chapter 3: A* search algorithm

Chapter 4: Soar (cognitive architecture)

Chapter 5: Heuristic

Chapter 6: Combinatorial explosion

Chapter 7: Logic Theorist

Chapter 8: Iterative deepening A*

Chapter 9: Means-ends analysis

Chapter 10: State space search

(II) Answering the public top questions about general problem solver.

(III) Real world examples for the usage of general problem solver in many fields.

Who This Book Is For

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of general problem solver.

What is Artificial Intelligence Series

The artificial intelligence book series provides comprehensive coverage in over 200 topics. Each ebook covers a specific Artificial Intelligence topic in depth, written by experts in the field. The series aims to give readers a thorough understanding of the concepts, techniques, history and applications of artificial intelligence. Topics covered include machine learning, deep learning, neural networks, computer vision, natural language processing, robotics, ethics and more. The ebooks are written for professionals, students, and anyone interested in learning about the latest developments in this rapidly advancing field.
The artificial intelligence book series provides an in-depth yet accessible exploration, from the fundamental concepts to the state-of-the-art research. With over 200 volumes, readers gain a thorough grounding in all aspects of Artificial Intelligence. The ebooks are designed to build knowledge systematically, with later volumes building on the foundations laid by earlier ones. This comprehensive series is an indispensable resource for anyone seeking to develop expertise in artificial intelligence.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: Jul 6, 2023

Book preview

Chapter 1: General Problem Solver

In 1957, Herbert A. Simon, J. C. Shaw, and Allen Newell (RAND Corporation) developed a computer program called General Problem Solver (GPS) with the intention of making it into a universal problem solver machine. The GPS employs a means-ends approach, in contrast to the defunct Logic Theorist project.

In principle, GPS can solve any problem that can be expressed as a directed graph with one or more sources (that is, axioms) and sinks (that is, desired conclusions) using well-formed formulas (WFFs) or Horn clauses. For instance, GPS can be used to prove results in the problem spaces of predicate logic and Euclidean geometry. It was based on the research of Simon and Newell on logic machines. By decoupling its problem-solving strategy from its problem-knowledge (represented as input data), GPS was the first computer program of its kind (a generic solver engine). IPL, a third-order programming language, was used to implement GPS.

Because search was easily lost in the combinatorial explosion, GPS could solve only trivial problems like the Towers of Hanoi that could be sufficiently formalized. A computationally infeasible number of walks through the inferential digraph was reached. (Even a simple state space search, like the Towers of Hanoi, can become computationally infeasible in practice, though judicious prunings of the state space can be achieved by such elementary AI techniques as A* and IDA*.).

In order to solve problems, the user defined objects and the operations that could be performed on those objects, and GPS generated heuristics through means-ends analysis. It zeroed in on the possible processes, determining which inputs worked and which ones produced results. Then, it set smaller objectives to accomplish along the way.

The AI architecture Soar is a direct descendant of the GPS paradigm.

{End Chapter 1}

Chapter 2: First-order logic

First-order logic is a set of formal systems that are used in the fields of mathematics, philosophy, linguistics, and computer science. Other names for first-order logic include predicate logic, quantificational logic, and first-order predicate calculus. In first-order logic, quantified variables take precedence over non-logical objects, and the use of sentences that contain variables is permitted. As a result, rather than making assertions such as Socrates is a man, one can make expressions of the form there exists x such that x is Socrates and x is a man, where there exists is a quantifier and x is a variable. In this way, propositional logic may be thought of as the basis for first-order logic.

A theory pertaining to a subject, such as set theory, a theory for groups, or a formal theory of arithmetic, is typically a first-order logic together with a specified domain of discourse (over which the quantified variables range), finitely many functions from that domain to itself, finitely many predicates defined on that domain, and a set of axioms that are believed to hold about them. Sometimes, in a more academic meaning, theory is believed to refer to nothing more than a collection of words in first-order logic.

First-order logic may be differentiated from higher-order logic by the use of the word first-order., which involve predicates that take other predicates or functions as input, quantification may be performed over predicates or functions alternatively, or both, are permitted.: 56 In first-order theories, sets and predicates are often seen working together.

In higher-order theories with their interpretations, It is possible to see predicates as collections of collections.

There are a lot of different deductive systems for first-order logic, and most of them are both valid and sound, all verifiable propositions are true in all models) and full (i.e.

It is possible to prove any proposition if it holds true across all models.

Despite the fact that the link between logical consequences is merely semidecidable, In first-order logic, automated theorem proving has seen significant advancements in recent years.

Additionally, first-order logic complies with a number of metalogical theorems, which enables it to be examined via the lens of proof theory, such as the Löwenheim–Skolem theorem and the compactness theorem.

The study of first-order logic, which serves as the industry standard for the formalization of mathematics into axioms, is included in the foundations of mathematical research. The axiomatization of number theory into first-order logic is known as Peano arithmetic, while the axiomatization of set theory into first-order logic is known as Zermelo–Fraenkel set theory. A structure having an infinite domain, such as the natural numbers or the real line, cannot be adequately described by any first-order theory since such a theory lacks the power necessary to do so. Stronger logics, such as second-order logic, make it possible to generate axiom systems that categorically describe both of these structures in their entirety. These are known as categorical axiom systems.

Gottlob Frege and Charles Sanders Peirce both made significant contributions to the development of first-order logic separately.

For more information on the development of first-order logic and the reasons it came to predominate formal logic, go here, see José Ferreirós (2001).

First-order logic, as contrast to propositional logic, is concerned with more straightforward declarative statements, although it also addresses predicates and quantification.

A predicate is a statement that evaluates to either true or false based on one or more things in the domain of discourse. Think about the fact that both Socrates is a philosopher and Plato is a philosopher are true. These statements are thought to have no connection to one another in propositional logic, and as such, they might be represented by variables such as p and q, for instance. Each of these phrases have the basic structure of a is a philosopher, which means that the predicate is a philosopher appears in both of them. In the first phrase, the variable an is represented by the name Socrates, while in the second sentence, the variable an is represented by the name Plato. In this particular example, the employment of predicates, such as is a philosopher, is permissible within the framework of first-order logic, while propositional logic does not.

Logical connectives allow one to express the nature of the relationships that exist between predicates. Take for instance the first-order rule that states, if an is a philosopher, then an is a scholar. This formulation is an example of a conditional statement, with the hypothesis being that a is a philosopher, and the conclusion being that a is a scholar. The validity of this equation is contingent not only on the nature of the thing signified by a, but also on how one understands the meanings of the predicates is a philosopher and is a scholar..

In a formula, quantifiers may be used in conjunction with variables. The value of the variable an in the above formula may be quantified globally by using, for example, the first-order phrase For any a, if an is a philosopher, then an is a scholar. The use of the universal quantifier for every in this statement conveys the concept that the assertion if an is a philosopher, then an is a scholar is true for any and all possible combinations of the letter a.

The logically equivalent opposite of the statement For any a, if an is a philosopher, then an is a scholar, which is the phrase There exists a such that an is a philosopher and an is not a scholar, is the statement There exists a such that an is not a scholar. The concept that the statement a is a philosopher and an is not a scholar is true for some choice of a is what the existential quantifier there exists is trying to communicate to us.

Both is a philosopher and is a scholar are examples of predicates that accept a single variable as an argument. In most cases, predicates are able to accept a number of variables. The predicate is the teacher of in the first-order phrase Socrates is the teacher of Plato has two variables that it is referring to.

An interpretation of a first-order formula, also known as a model, clarifies the meaning of each predicate and identifies the entities that are capable of instantiating the variables. The domain of discourse, often known as the universe, is typically expected to be a set that is not empty. These things make up the universe. For instance, in an interpretation in which the domain of discourse consists of all human beings and the predicate is a philosopher is understood as was the author of the Republic, the sentence There exists such a person that such a person is a philosopher is considered to be true, as Plato was the one who witnessed it.

In first-order logic, there are two fundamental components. In first-order logic, well-formed expressions are determined to be finite sequences of symbols according to the syntax, while the meanings of these expressions are determined according to the semantics of the language.

The language of first-order logic, in contrast to natural languages such as English, is entirely formal. As a result, it is possible to assess, in a mechanized manner, whether or not a particular sentence is correctly constructed. Well-formed expressions may be broken down into two primary categories: words, which intuitively describe things, and formulae, which intuitively convey propositions that can be either true or untrue. In first-order logic, the words and formulae are represented by strings of symbols, and the alphabet of the language is formed by the symbols themselves in their whole. Formal logic cannot be applied to the nature of the symbols themselves, as is the case with all formal languages; yet, most people consider them to be nothing more than letters and punctuation marks.

It is usual practice to separate the letters of the alphabet into their corresponding logical symbols, They are usually understood to imply the same thing, in addition to illogical symbols, Its meaning is dependent on how it is interpreted.

For example, the logical symbol \land always represents and; It is never used to mean or in any context, which is represented by the logical symbol \lor .

However, One possible interpretation of a non-logical predicate symbol such as Phil(x) is that it means x is a philosopher., the person x is known as Philip, or any other unary predicate, depending on the interpretation that is being applied at the time.

Logical symbols are a collection of characters that may look different depending on who creates them, but they often consist of the following::

Quantifier symbols: ∀ for universal quantification, and ∃ for existential quantification

Logical connectives: ∧ for conjunction, ∨ for disjunction, → for implication, ↔ for biconditional, ¬ for negation.

Some authors use Cpq instead of → and Epq instead of ↔, especially in contexts