Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

чуть-чуть об алгоритмах (англ.)

(может быть интересно читателям со склонностью к математике, компьютерам итп.)

Тьюринг доказал в 1936-м году, что невозможно решить проблему остановки: невозможно написать такую программу, которая сможет, получив на входе описание алгоритма, определить безошибочно, остановится этот алгоритм когда-нибудь, если его запустить, или нет. Эта задача принципиально неразрешима.

В одном обсуждении один из участников написал, что ему не нравится в доказательстве неразрешимости тот факт, что гипотетическая программа, которая может решить проблему остановки, запускает в некотором смысле "сама себя", и противоречие получается от того, что она не может решить проблему остановки для себя самой (или, точнее, немного расширенную версию себя самой). Ведь вообще-то нас интересуют реальные программы; если бы у нас была программа, умеющая решать проблему остановки, мы бы запускали ее на реальных программах, а не на "ней самой"; если бы она вдруг на себе самой не работала, это бы нам и не мешало. Т.е. доказательство верно, конечно, но остается ощущение, что это такая техническая победа, а не настоящая. В ответ я написал нижеследующий длинный комментарий по-английски, о природе алгоритмов и доказательствах неразрешимости проблем.

Algorithms are clever ways to pack up an infinity of data into a finite description.

Say there’s an infinite (here and below “infinite” means “countably infinite”; if you don’t know what that means, ignore this remark) binary string of zeroes and ones, some 010010101101111… Suppose I come up to you and I say: “I am the keeper of this infinite string of data. People come to me and ask: what is at the 13th place in this string, 0 or 1? How about 23523238th place? For any query they ask, I think for a while and then give them the correct answer. But I’ve been doing this for a long time and could use a vacation. Could you take over for me for a while? The job pays well.”

You might reply to me: “I will think about your offer seriously the moment I understand how you propose that I do it. How are you going to teach me your job? If the string were finite, you could just write it on a (possibly very long) piece of paper, and I could keep the piece of paper and consult it. But it’s infinite. No piece of paper will hold it. In fact, I wonder how *you* manage to answer people’s queries truthfully in the first place!”

But what if the string of data, though infinite, actually has some pretty simple and definite structure? Like maybe it’s all alternating 0101010101… to infinity, or maybe it’s the binary representation of the digits of pi. Then it’s easy for me to take over your job. You just write down the way for me to access any part of the string on demand – like “odd places are 0s, even places are 1s”, or “[formula for calculating pi to any desired accuracy]“. These descriptions are finite in length, so they *can* be written down and passed on. Armed with such a recipe, I can answer people’s queries, and you go on vacation. These clever recipes for packing up an infinite string of data in a finite description are algorithms.

There are many many more infinite strings of data than there are finite clever recipes for specifying one particular infinite string. This has to do with the fact that there are different orders of infinity, some larger than others, and the infinity of all the possible infinite strings of data is much much larger than the infinity of all the possible finite descriptions. So in fact, only a tiny minuscule incomprehensibly tiny minority of all infinite strings of data could ever be “teachable”, that is, specified by an algorithm. By any reasonable way of accounting just about all of them aren’t “teachable”. But we don’t know which are and which aren’t.

Say we have a problem. Here I need to be careful because there are many genuine problems (like, I dunno, “Is the Riemann hypothesis provable?”) that have a very short finite description (either “yes” or “no”), but we don’t know what it is. This isn’t the kind of problem I’m talking about. In the context of non-computability we’re talking about problems which have an infinite variety of inputs (“queries”), each of which needs its own separate output (“answer”). Like “given this number, what is the value of pi at this place?”. Or “given this description of an algorithm, does it ever halt?”. So, when we have such a problem, it’s usually a simple matter to represent it as an infinite binary string of 0s and 1s. For example, with binary digits of pi it already has this structure. For the problem "given an algorithm, does it ever halt?" we might use a simple way to enumerate all possible algorithms, and then our string will have 1 at the N-th place if the N-th algorithm halts, and 0 otherwise.

Anyway, whatever the problem is, translating it into "answer queries about this infinite binary string of data" is usually east. And the question then is, is this string one of the “teachable” ones, does there exist a finite clever description for it? Note: not “do we *have* a finite clever description for it?”, but “does there exist one?”. If we have an algorithm, that’s fine, we’re done. If we don’t have one, perhaps we will one day? Maybe our descendants will be much smarter than us and come up with one? Algorithms are clever descriptions, and the cleverness goes up and up and up unbounded. There’re certainly many clever algorithms that are much too complicated for our puny brains. Who’s to say that one of them doesn’t describe our problem?

Because cleverness of algorithms is seemingly unbounded, nobody’s been able to *prove* a particular problem “unteachable” by explicitly considering possible ways to describe it. How would such an attempt look like? Imagine a naive person who learned about pi, and they say: “Clearly it’s impossible to calculate more
than a few digits of pi. How would you even do it? You can draw a circle in the sand, measure its length and diameter, divide… but the accuracy is very limited. Maybe you could blow up a very very accurately round piece of glass, and use a piece of string to measure its diameter very precisely… maybe you’d get 1-2 more digits this way. But that’s it, you’ll never improve on these”. Then you teach them trigonometry, infinite series, and explain painstakingly that here’s a series that sums up to pi and all we need to do to get more digits is to keep calculating. “Oh… I didn’t know that was possible.” But of course, that person’s conviction before you showed them trig was only conviction, not *proof*. Nobody knows how to bar explicitly all unknown clever ways of finding out something, so nobody has been able to prove some infinite string “unteachable” this way.

The only way we have of proving that some infinite string is unteachable is to include information about all the possible algorithms inside the string. This is easier than it sounds, since there’s “only“ an infinity of possible algorithms, and the string is also infinite. So our only method to outsmart all the clever algorithms, including those too clever for our brains, is to say – oh, this problem is so smart that it already knows something about any one of you. This string of data has such a *rich structure* that no clever algorithm will ever describe it, because it knows something about *any* possible algorithm that it can use to defy its attempt to accurately describe it.

This is completely transparent with the Halting Problem, because basically that’s what it is – an infinite string that has “dirt“ on every possible algorithm. But all the other problems that have been proven non-computable are inevitably like this too, it’s just that their *rich structure* is not so obvious and we needed to work hard to uncover it. Maybe there’s a problem in group theory that merely looks hard, but then someone comes along and proves that it has such a rich structure that its infinite string of data actually contains dirt on all possible algorithms, just as the halting problem; you just need to understand how to dress up algorithms as groups in a particularly clever way, so that truths about algorithms become truths about groups that your string has dirt on. All the undecidability results (in this sense of non-computability) have been like this. There’s no other method of getting them.

But what this also means is that while the objection to the Halting Problem undecidability proof, that “P was forced to act on itself, even though it’s sort of a black box”, is understandable, it’s really unavoidable. If we want to *prove* that some infinite string of data is unteachable – not just “be really sure”, but *prove* – we’d better have an argument to applies to any possible finite description and shows that it can’t work. Because there’re descriptions far too clever for our brains, we can only hope to address every possible description by imagining that it exists as a “black box”. But then the only thing we know about it is that it (ostensibly) solves the problem, and at the same time the problem contains “dirt” on it, just as it does on any possible description. Out of these two pieces of information we have to conjure a contradiction; so applying the “black box” to something we construct with the help of the “dirt” on it is just about the only thing we can hope to do. Fortunately, it works.
Tags: всячина
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 30 comments