Comments about "Halting problem" in Wikipedia

This document contains comments about the article Halting problem in Wikipedia
In the last paragraph I explain my own opinion.

Contents

Reflection

Introduction

The article starts with the following sentence.
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever.
This sentence is not clear
The purpose of a description of a program should be to explain what the purpose of a program is i.e the purpose of the program "Adding" is to add three numbers.
To mention, as part of this description, if the program terminates or runs forever is not necessary.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
You can only prove that you can solve a certain problem by writing an algorithm and running the program on a computer.
The 'reverse' is not possible.
Jack Copeland attributes the term halting problem to Martin Davis.
In the book "Computer power and Human Reason" at page 63 we read:
Turing answered that question as well: a Turing machine can be built to realize any process that could naturally be called an effective procedure.
That is the type of issue we should be concerned with and not if a program terminates or runs forever.

1. Background

The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input.
This is not an issue.
While deciding whether these programs halt is simple, more complex programs prove problematic.
This demonstrates my understanding that the halting problem is not a problem.
One approach to the problem might be to run the program for some number of steps and check if it halts. But if the program does not halt, it is unknown whether the program will eventually halt or run forever.
A silly sentence.
Turing proved no algorithm exists that always correctly decides whether, for a given arbitrary program and input, the program halts when run with that input.
What is the purpose?
It is the otherway around. You should be able to prove that there are programs which solve certain problems.

1.1 Programming consequences

Some infinite loops can be quite useful. For instance, event loops are typically coded as infinite loops
In an computer you have what are called interrupts (events) and interrupt handlers. Interrupts in some sense is an electrical responds after a request to some hardware. For example you can 'ask' a printer to print a text message. When the printer is finished the printer causes an interrupt to indicate that the task is finished. This interrupt is linked to an interrupt handler which 'asks' the printer to print the next line, until the whole letter is printed.
To think that the interrupt handler is an infinite loop is wrong, because most of the time the interrupt handler is dormant.

1.2 Common pitfalls

2 History

2.1 Timeline

3. Formalization

3.1 Representation as a set

3.2 Proof concept

3.3 Sketch of proof

4 Computability theory

4.1 Gödel's incompleteness theorems

5 Generalization

5.1 Halting on all inputs

5.2 Recognizing partial solutions

5.3 Oracle machines

6. See also

Following is a list with "Comments in Wikipedia" about related subjects

7. Notes

In none of his work did Turing use the word "halting" or "termination". Turing's biographer Hodges does not have the word "halting" or words "halting problem" in his index.
I can imagine that Turing never used the word halting or termination, at least not in the sense explained in Introduction : "whether the program will finish running or continue to run forever" because any such prove 'does not make sense'.

Reflection 1 - What is a clear program description

I will not go into the details of what is a clear or unambigous program description.
What is important that the description should contain a man machine interface. Such a man machine interface describes all the inputs (commands) to operate the program. For all the inputs the man machine interface should clearly defined what the purpose is and what the valid values are. When invalid values are entered the man machine interface should indicate this and prevent that the program can not start. The object is that you will only run the actual program under valid conditions and that the program does not contain any error.

Reflection 2 - Computer Power and Human Reason.

This excellent book by Joseph Weizenbaum at page 65 reads:
We may, foe example, be interested to know whether some machine we have designed, say, our adding machine, will halt once started with a particular data set. If would be convenient if we had a tseting machine which could, for any machine and any data set appropiate to it, tell us whether that machine operating on the given data set would ever halt. No such machine can be built.
The adding machine meant is described in the pages 56 to 58 of that book.
The problem is what is the meaning of the word halt in this context. IMO the question is much more: does the adding machine calculate the correct answer on any data set? or much shorter: does the adding machine always work?.
The normal aproach is to perform certain tests and observe the results.
See also: Reflection 1 - What is a clear program description
In a broader sense this is a physical/mechanical issue which can not be solved on any computer.

Feedback

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

Go Back to Wikipedia Comments in Wikipedia documents
Back to my home page Index