• The text in italics is copied from that url
• Immediate followed by some comments
In the last paragraph I explain my own opinion.

### Introduction

The article starts with the following sentence.
The Entscheidungsproblem (German, "decision problem") is a famous problem of mathematics.
I don't understand that this is such a famous problem. The importance is that it was designed as part of the Turing machine
David Hilbert formulated the problem in 1928: Is there an algorithm that will take a formal language, and a logical statement in that language, and that will output "True" or "False", depending on the truth value of the statement?
Was is the truth value of a statement?
Each logical statement of any formal language is true.
All combinations of logical statements of any formal language is true.
As such it can never be proven if any program is true or false. (It is always true).
When you make any change to any program the previous edition becomes false and the new one becomes true.
The whole question is if any program (any logical combination) makes sense..
The answer is in the opinion of the auther and is clearly: No.
The algorithm does not tell how it reaches the answer, nor prove it, as long as the answer is always correct.
n 1936 and 1937, Alonzo Church and Alan Turing showed independently, that there can be no answer to the Entscheidungsproblem.
Okay.
They showed that it is impossible for an algorithm to decide whether statements in arithmetic are true or false.
You cannot show that. You can only accept that.
For this reason, there can be no solution for the Entscheidungsproblem.
When you accept that there is no solution.

### Reflection 1 - Prove

The general problem is that you cannot prove that a program is correct.
The only thing that you can do is to divide the program in parts (subroutines) and to prove each part (subroutine). Prove in that sense means to incorparate the subroutine into a program which sole task it to test the subroutine for as many test cases as possible.
A task can be one logical statement in a higher level language or one logical statement of a lower level language (assembly language).

### Feedback

If you want to give a comment you can use the following form Comment form
Created: 29 September 2018

Go Back to Wikipedia Comments in Wikipedia documents