Entscheidungsproblem

It is fair to say that the knowledge and opinion on how to treat multiple myeloma are evolving. The regimen that the French government has provided for the wife is not yet available in England and Wales because NICE have not yet, perhaps, completed their bean counting cost benefit analysis. The situation is different in Scotland.

All the studies I have found so far in the literature are “old” and have used less effective treatments before high dose chemotherapy / autologous stem cell transplants. This one published in the New England Journal of Medicine {2003} has 200 people in each of the groupings, one for single stem cell transplant and one for tandem. That is not a large sample, so a 95% confidence interval does not fill me with confidence. This kind of epidemiology cannot take into consideration the very heterogenous nature of the disease. It is difficult to conclude specifically from the general, though there may be a temptation so to do. One cannot ask, “tell it to me straight Doc, how long have I got?”

The graphs for overall survival diverge significantly at ~ 48 months. Before that they are roughly colinear up to ~36 months.

The other graph here is for event free survival which means no relapse. From this limited data set the second transplant has a better impact on avoiding “events”.

I will be digging into this in more detail over the coming days.

Since I was stupid enough to agree to develop a course on decision making, I have been very interested in the act of deciding. Being real we have to ask, “would you prefer to die in France or the UK?” We know that it is impractical in the long term for me alone to maintain the garden at a standard that I/we would be happy with. Therefore, the decision to move has in effect been made. We also know that at some stage the disease will return, it is incurable. There are many unknowns and for the time being some unknowables.

This illness arrived during a global pandemic and is being treated as there is a war on mainland Europe. Energy and food security are insecure, and it looks like the economies are going into a very inflationary epoch.

I guess the best way to live with this incurable thing is to remain as present focussed as possible but there has to be some sense of what do we do, how might we best place ourselves moving forward.

We have one strong criterion for a new abode and that is relative proximity to a hospital specialising in myeloma treatment.

There is an upcoming decision, which may not be ours to make concerning a second high dose chemotherapy / stem cell transplant.

We know we could afford a smaller abode in France; the choice of area is much more limited in the UK unless of course there is a massive crash in the housing market.

The decision making funnel is open…

From Wikipedia, the free encyclopedia

In mathematics and computer science, the Entscheidungsproblem (pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm], German for “decision problem”) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers “Yes” or “No” according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms.

Completeness theorem

By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the Entscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.

In 1936, Alonzo Church and Alan Turing published independent papers showing that a general solution to the Entscheidungsproblem is impossible, assuming that the intuitive notion of “effectively calculable” is captured by the functions computable by a Turing machine (or equivalently, by those expressible in the lambda calculus). This assumption is now known as the Church–Turing thesis.

History of the problem

The origin of the Entscheidungsproblem goes back to Gottfried Leibniz, who in the seventeenth century, after having constructed a successful mechanical calculating machine, dreamt of building a machine that could manipulate symbols in order to determine the truth values of mathematical statements. He realized that the first step would have to be a clean formal language, and much of his subsequent work was directed toward that goal. In 1928, David Hilbert and Wilhelm Ackermann posed the question in the form outlined above.

In continuation of his “program”, Hilbert posed three questions at an international conference in 1928, the third of which became known as “Hilbert’s Entscheidungsproblem“. In 1929, Moses Schönfinkel published one paper on special cases of the decision problem, that was prepared by Paul Bernays.

As late as 1930, Hilbert believed that there would be no such thing as an unsolvable problem.

Negative answer

Before the question could be answered, the notion of “algorithm” had to be formally defined. This was done by Alonzo Church in 1935 with the concept of “effective calculability” based on his λ-calculus, and by Alan Turing the next year with his concept of Turing machines. Turing immediately recognized that these are equivalent models of computation.

The negative answer to the Entscheidungsproblem was then given by Alonzo Church in 1935–36 (Church’s theorem) and independently shortly thereafter by Alan Turing in 1936 (Turing’s proof). Church proved that there is no computable function which decides, for two given λ-calculus expressions, whether they are equivalent or not. He relied heavily on earlier work by Stephen Kleene. Turing reduced the question of the existence of an ‘algorithm’ or ‘general method’ able to solve the Entscheidungsproblem to the question of the existence of a ‘general method’ which decides whether any given Turing machine halts or not (the halting problem). If ‘algorithm’ is understood as meaning a method that can be represented as a Turing machine, and with the answer to the latter question negative (in general), the question about the existence of an algorithm for the Entscheidungsproblem also must be negative (in general). In his 1936 paper, Turing says: “Corresponding to each computing machine ‘it’ we construct a formula ‘Un(it)’ and we show that, if there is a general method for determining whether ‘Un(it)’ is provable, then there is a general method for determining whether ‘it’ ever prints 0”.

The work of both Church and Turing was heavily influenced by Kurt Gödel’s earlier work on his incompleteness theorem, especially by the method of assigning numbers (a Gödel numbering) to logical formulas in order to reduce logic to arithmetic.

The Entscheidungsproblem is related to Hilbert’s tenth problem, which asks for an algorithm to decide whether Diophantine equations have a solution. The non-existence of such an algorithm, established by the work of Yuri Matiyasevich, Julia Robinson, Martin Davis, and Hilary Putnam, with the final piece of the proof in 1970, also implies a negative answer to the Entscheidungsproblem.

Some first-order theories are algorithmically decidable; examples of this include Presburger arithmetic, real closed fields, and static type systems of many programming languages. The general first-order theory of the natural numbers expressed in Peano’s axioms cannot be decided with an algorithm, however.