Entscheidungsproblem

In mathematics and computer science, the Entscheidungsproblem is a famous challenge. It asks if there is a way to always know whether a math statement is true or not.

It was first posed in 1928 by two smart thinkers named David Hilbert and Wilhelm Ackermann. They wondered if there could be a special method to follow that would tell us if any given statement is always true.

Later, in 1936, Alonzo Church and Alan Turing showed that such a perfect method does not exist. This discovery helped shape our understanding of what computers can and cannot do. It tells us that some problems are so hard that even the best computers would never finish solving them.

The Entscheidungsproblem remains an important idea in how we study math and computing today.

Completeness theorem

A statement is true for everyone and everything if we can prove it using special rules and ideas from logic. The Entscheidungsproblem asks if there is a way to always know if a statement can be proven true using these logic rules.

In 1936, Alonzo Church and Alan Turing showed that there is no single method that can always decide if a statement can be proven true this way. They believed that what people can calculate with simple steps is the same as what a special kind of machine, called a Turing machine, can do. This idea is now called the Church–Turing thesis.

History

The idea of the Entscheidungsproblem began with Gottfried Leibniz in the 1600s. After making a machine that could do calculations, he wanted a machine that could decide if math statements were true or false. He knew he needed a clear way to write math problems first.

Later, in 1928, David Hilbert and Wilhelm Ackermann asked this question at a big meeting. Even in 1930, Hilbert thought every problem could be solved.

Negative answer

Before scientists could answer this big question, they needed to clearly define what an “algorithm” is. Two important thinkers helped with this: Alonzo Church in 1935 and Alan Turing in 1936. They showed that their ideas about solving problems were actually the same.

Later, Church and Turing proved that there is no way to create a single method that can always tell if a math statement is true or not. This showed the limits of what computers and math can solve. Their work built on earlier ideas from Kurt Gödel, who showed that some math truths can’t be proven using certain rules.

Generalizations

Main article: Decidability (logic) § Decidability of a theory

The Entscheidungsproblem is about finding a way to know if a math statement is always true. Using special math rules, it helps decide if one statement comes from a group of statements. But some math systems with endless rules can't be solved this way.

Some math systems can be solved with steps, like Presburger arithmetic, real closed fields, and type systems in many programming languages. However, the system of natural numbers with addition and multiplication, called Peano's axioms, can't be solved with a simple step-by-step method.

Fragments

The classical Entscheidungsproblem asks if a statement in logic is always true. A special version asks if it is true only in small situations. A famous result shows that this smaller version cannot be solved by any computer program.

Some basic ideas help us understand these problems:

• S a t ( Φ ) asks if there is any situation where a set of statements Φ is true.
• F i n S a t ( Φ ) is the same question, but only for small situations.

A logical fragment is a set of statements with certain rules. We can ask if a set of statements in that fragment has any true situation. Some fragments are easy to solve, while others are very hard or impossible to solve with a computer program.

Aristotelian and relational

Aristotelian logic uses simple statements like "All cats are animals" or "Some dogs are friendly". These can be written as special types of logical statements. Deciding if such a set of statements has any true situation can be done with a computer, but it takes time and memory.

Relational logic adds more complex statements, like "Every person loves someone". Even with these, we can still decide if a set of statements has any true situation, but it also takes time and memory.

Arity

When we limit the number of variables in our statements, some become very hard to solve. For example, with just two variables, it is very hard to decide if a statement is true in any situation. With three variables, it is impossible to decide for some types of statements.

The monadic predicate calculus uses only statements about single things, like "This apple is red". Deciding if such a set of statements has any true situation is very hard, but possible.

Quantifier prefix

Statements can be built with words like "for all" (∀) and "there exists" (∃) in different orders. For example, a statement might say "For every person, there exists a friend". The order of these words changes how hard it is to decide if the statement is true in any situation.

Some orders, like "For all, there exists, for all", are impossible to decide with a computer program. Others, like "There exists, for all, there exists", can be decided, as shown by early mathematicians. Still others take a lot of time and memory to decide.

Börger and others have studied how hard it is to decide these statements for every possible combination of rules.

Practical decision procedures

It is important to have ways to quickly decide if some math statements are true or false. This helps us check computer programs and electronic circuits. For simple yes-or-no questions about logic, we use special methods called SAT-solving.

For harder math problems, we have different tools. For example, questions about straight-line numbers can be solved using the simplex algorithm. For whole-number questions, we use Cooper's algorithm or William Pugh’s Omega test. When problems mix yes-or-no logic with math, we use SMT-solving. This brings together different problem-solving methods. There are also ways to solve questions about real numbers, using important math results and computer methods.