Доказателство, че има най-малко една тривиална компютърна програма, която не може да съществува

Най-красивите математически доказателства, кн. 2, Maxime Coutte.

Статията от миналата седмица беше на тема „Някои безкрайности са по-големи от другите?“ и аргументът на Кантор Диагонал. Тази седмица искам да споделя един от любимите ми теоретични проблеми на компютърните науки.

„Части от четири ранни компютъра, 1962 г. Отляво надясно: дъска ENIAC, борд EDVAC, платка ORDVAC и платка BRLESC-I, показваща тенденцията към миниатюризация.“

Спомням си още в средното училище, когато започнах да се занимавам с компютърни науки, реших, че теоретично мога да реша всеки изчислителен проблем с правилните математически инструменти и програмиране. Сгреших. Има теоретично ограничение за всяка компютърна машина и тук ще видим доказателството, че има поне един логически проблем, който никоя компютърна програма никога няма да може да реши.

Определяне на Н, невъзможната компютърна програма

Определяме Компютърна програма P (i) като списък от инструкции P, които, когато се изпълняват с вход i, дават изход o.

Например,

е програма, която обобщава двете числа, които давате като входни данни, и,

е програма, която използва друга програма - P_add - като вход и предава тази програма на другите два входа. Той прави това, което прави P_add (a, b), и го удвоява.

Когато една програма се изпълни, тя може да се забие, да работи завинаги и никога да не извежда нищо, например програма P_sum, която пристъпва към сумата от всички естествени числа, ще продължи да добавя естествени числа завинаги, без да завършва някога (т.е. да спре) и извеждане на резултата.

Сега нека предположим, че съществува програма H (P, i), която приема като вход списъка с инструкции P на програмата P (i) и i входът на P (i), и извежда a 1, ако P (i) спрете в някакъв момент и 0, ако P (i) се забие и работи завинаги. Казано по-просто,

Защо списъкът с логически инструкции H не може да съществува

Въз основа на доказателството на Алън Тюринг в статията „За изчислимите числа с приложение към Entscheidungsproblem“ -1937, ние ще докажем, че H не може да съществува.

Въз основа на предположението, че H съществува, ние изграждаме програма X (P), която работи завинаги, ако и само ако H (P, P) = 1 и спре, ако и само ако H (P, P) = 0. С други думи,

Вече можем да разгледаме дали X (i) свой собствен списък с инструкции X като вход: X (X).

Следователно X (X) работи завинаги, ако и само ако H (X, X) = 1 и X (X) спре, ако и само ако H (X, X) = 0. С други думи,

Имаме противоречие! От Reductio ad absurdum показахме, че H не може да съществува, тъй като съществуването му води до абсурдни заключения.

Следователно компютърна програма, която може да определи дали някоя Компютърна програма, дадена с някакъв вход, ще бъде заседнала и ще работи завинаги или завърши да работи, е невъзможно. Има поне една компютърна програма, която решава логически проблем, който не може да съществува.

Референции, Алън Тюринг. „На изчислими числа, с приложение към Entscheidungsproblem“. 1937.

Аз съм Max Coutte, съосновател на Relativty.com, VR слушалки, проектирани от нулата, от които отварях кода и хардуера. Следвайте ме в Twitter @maxcoutte.