An Opinionated Guide to Computability and Complexity (Post #0)

post by Noosphere89 (sharmake-farah) · 2023-07-24T17:53:18.551Z · LW · GW · 10 comments

Contents

  What the Church-Turing Thesis will look like in the sequence
None
10 comments

Today, I'll try to introduce certain things in this sequence I will make that I found interesting of computability and complexity theory is, and in particular show how many problems can be solved by computers, in both a philosophical and practical sense. I will mostly not be reviewing the history of computability theory and complexity theory, except as a brief aside.

Along the way, I'll introduce some commentary of my own, so this will at least be somewhat interesting, as it would be boring to only talk about it, without interacting with the subject.

I will mostly be using the terms computability and complexity theory for historical reasons, but note that this will not correspond to decidable and practically solvable problems always, and we must always pick a machine and constraints on the machine before we can talk about whether a problem is solvable at all.

Things I will cover include:

1. Why the definition of decidable problems is machine and constraint dependent, and why picking different machines will get you different results in what you can compute, and why picking different time and space requirements will affect the sets of things you can compute.

2. Why Hilbert was right, in a manner of speaking, to hope for an algorithm that could decide at least major parts of mathematics, and why Church and Turing's thesis that the Turing Machine could capture every computer and algorithm was false.

3. Why Cobham's thesis that the practical problems we can solve correspond to P in complexity theory in our specific universe is unlikely to be true, because of the Time Hierarchy theorem as well as issues with the constant potentially being arbitrarily large.

4. What philosophy can gain from understanding complexity and computability theory, and addressing Aaronson's paper to point out where it goes right and wrong.

5. The underappreciated amount of things a Universal/Complete Turing Machine can simulate, and that it can actually emulate a halting oracle, even if it couldn't solve the halting problem on it's own, and the implications of that observation. Equivalently, I'm trying to say that computability and simulatability are different concepts, and one can simulate something without you being able to solve the computational problem it's doing.

6. What problems could we solve over the very long future, and what would we need to be able to do or know in order to solve difficult problems like the halting problem or the TQBF problem.

7. And much more!\

What the Church-Turing Thesis will look like in the sequence

This has been a common question, and some people have disputed my picture of the Church-Turing Thesis, because they disagreed with me around what the problem was, and especially both the constraints and whether it was a universal claim, or an existential claim.

For the purposes of this sequence, it will be defined the following way:

For the purposes of the Church-Turing Thesis, I will define the claim by Church and Turing like this, to translate what I think they wanted to conjecture.

The Church-Turing Thesis/Conjecture is captured by the first point below:

The Universal Turing Machine, or equivalently a human with unlimited time and memory can compute all the functions that are calculable by effective functions, as defined below.

Effectively calculable functions have the following constraints/rules:

2.1 They must always give an answer in finite time, but the time bound can be arbitrarily large, and the space required to solve a problem may be unbounded, but never infinite, just arbitrarily large.

2.2 The human is assumed to have unlimited paper to act as a memory, and unlimited time to compute (They are immortal.)

2.3 The original condition has been replaced by the following condition below from Rafael Harth:

In this setting, we call a problem decidable iff there exists a single, fixed procedure that can take arbitrary instances of this problem and always behaves like this:

If the correct answer is 'yes', it outputs 'yes'. If the correct answer is 'no', it outputs 'no'.

The original statement is included below for completeness:

Its instructions need only to be followed rigorously to succeed. In other words, it requires no ingenuity to succeed.[4]

2.4 This condition is quoted below:

It consists of a finite number of exact, finite instructions.

2.5 Arbitrary extensions to the UTM are valid as long as they obey the constraints above.

2.6 Alternatively, any algorithm or effective method as defined in this post is allowed to be used so long as it is simulatable by a UTM, even multiple UTMs are allowed to simulate something.

Essentially, we can choose to use 2.5 or 2.6 as a condition, and it will be clear that adding either one causes a contradiction, in that we can enlarge the set of functions we can compute beyond the computable functions, thus causing a contradiction, and thus showing it is false.

Critically, it needs to hold for every algorithm/machine following the constraints, and any failure breaks the thesis.

10 comments

Comments sorted by top scores.