Не только математическая модель с бесконечной памятью для вычислительной машины
Я пишу архитектуру для Вычислительной машины с центральным процессором и лучами данных, которая может использовать неограниченную память. Размеры используемой памяти нынешними компьютерами ограничены разрядностью процессора и пропускной способностью каналов связи к ячейкам памяти. Впрочем, пропускная способность на практике всегда достаточна для полного использования разрядности.
А мне нужна такая модель (которую в принципе можно реализовать на практике) которая может оперировать со сколь угодно большой памятью, не меняя при этом ни центральный процессор (разрядность не меняется), ни ранее поставленную память. Можно просто доращивать любой луч данных любым количеством ячеек памяти.
Модель (Машина исполнения компьютерных алгоритмов) нужна как стандартная интерпретация для Теории компьютерных строк. Препринт - http://psta.psiras.ru/read/CompuStrTheory_08.06.2020.pdf
Получается работа больше чем на 100 страниц А4 в Ворде с изложением архитектуры нужной Машины. Перечитываю и правлю уже месяца 3 а ещё 3 месяца до этого нащупывал и менял подходы. Но сейчас вроде уже близко к окончанию.
Я не мог избежать аккуратного и трудоемкого построения данной модели (хотя хотел избежать и искал лазейки - я очень далёк от «героизма» всё же :) ) - после того, как заметил, что не могу «просто» сослаться на современные компьютеры и «представить», что их память бесконечна. Современные компы в принципе ограничены в размере строк при строковых операциях и никакое увеличение разрядности не делает конечное бесконечным даже в понимании «потенциально бесконечное».
А написать «можно построить архитектуру вычислительной системы с бесконечной памятью для строковых операций» - это заведомо получить предложение построить такую архитектуру для подтверждения своих слов. Я же не буду врать, что не заметил, что реальные компьютеры не масштабируются на бесконечность - я же заметил. И даже наврав - я этим никак не решу принципиальный вопрос. Да ещё и людей подставлю, которые дали мне возможность публиковаться. Так что, выбора не было.
Но сейчас хочу сказать не об этом, а об интересных отношениях между теорией и моделью, которые обнаружились, когда я решал вопросы с архитектурой Машины.
1. Граница между логикой модели и логикой теории
Логика модели всегда богаче логики самой теории. Это как гармонические колебания и приложения для них - пружинные мятники, электрические контуры, маятник в гравитационном поле. Вопрос - где проходит граница между свойствами, которые надо включать в теорию и которые остаются только в модели?
Вот у меня в теории доказана метатеорема об обязательном наличии стандартной интерпретации для любого решения в рамках арифметики. То есть - всегда есть вариант представить числа «счётными палочками» и применить любые арифметические теории к этой модели. Даже если данные теории строили для чисел в позиционной (десятичной, например) записи и работе алгоритмов с ними. А нет - не получается категоричность в этом для арифметики.
Именно поэтому нужна теория строк - иначе нет разницы между алгоритмами, работающими со «счётными палочками», которыми записаны «гёделевы номера» строк и самими строками. А это - экспоненциально большая (огромная) разница.
Но, с другой стороны, время не является частью теории строк. Потому что строки можно записывать и на лучах данных, когда доступ к ним линеен относительно позиции (номера) символа, и в «кубах» данных, когда время доступа будет порядка кубического корня от позиции символа в строке.
Поэтому возникает вопрос: я не включаю время в логику теории, но имею время в логике модели. И при этом я требую, чтобы размер строки был включён именно в логику теории, не соглашаясь с тем, что пусть размер тоже будет в логике модели, а не в логике теории.
А дело-то вовсе не в теории, а в семантике. Мы понимаем строки именно как последовательность символов «друг за другом» и должны строить теорию в соответствии с этой семантикой. И эта семантика требует, чтобы размер строки был однозначен, как и последовательность символов в ней. И тогда да, есть множество способов использовать эту строку и они потребуют разного времени.
При этом семантика для строк сложилась в ИТ-сообществе и поэтому никакого выбора нет, есть императив - изложить эту семантику на языке аксиом. А семантика такова, что время не привязано однозначно к строке, а вот размер и последовательность символов - должны быть однозначными и задаваться логикой теории.
2. А как же теорема Левенгейма-Сколема?
Но ведь есть теорема Левенгейма-Сколема, например, о том, что всё, что верно для действительных чисел в теории первого порядка верно и для некоторой счётной модели. То есть - не обязательна даже «несчётность».
Но ответ в том, что «несчётность» действительно не обязательна для той же непрерывности. Просто оказалось, что несчётность не может быть значимым свойством для каких-то понятных явлений. Категрично понятие несчётности можно сформулировать только в теории 2-го порядка (там Левенгейм-Сколем не верен), а понять теорию 2-го порядка там, где она не сводится к теории 1-го порядка - не получается, вообще говоря. Поэтому понятный нам смысл есть только у таких свойств действительных чисел, например, которые имеют полные аналоги на некоторых счётных моделях.
В этом смысле теорема Левенгейма-Сколема доказала, что несчётность модели не может быть значимой ни для какого понятного нам явления или свойства. А вот размер строки как раз является значимым и понятным нам свойством с понятными последствиями.
Как раз тот человек, который помогал мне готовить публикацию (и которого я так задерживаю) - вот с ним мы и пообсуждали летом 2020 г. про непрерывность, например, которая что для действительных чисел, что для рациональных - одно и то же, по сути. И это помогло мне понять, в чём отличие теоремы Левенгейма-Сколема от моей метатеоремы об обязательном наличии стандартной интерпретации у теорем арифметики. От Левенгейма-Сколема невозможно избавится - но это и не нужно, потому что верно для всех теорий 1-го порядка. А вот от арифметической стандартной интерпретации избавится можно и нужно - потому что она противоречит семантике строк и есть теория 1-го порядка без неё.
3. Примат целостности - его отрицание в теории первого порядка противоречиво.
Вот у строк есть такое свойство, что можно прочитать первый символ и сделать выводы, при этом не читая всех остальных символов после. Для модели «лучей данных» данное утверждение верно, по крайней мере. А в другой модели первым на луче может быть последний символ.
Но вот для чисел в стандартной интерпретации такая «частичность» чтения и возможность при этом делать выводы о части (какой символ в начале) - исключена. У меня в препринте есть довольно красивое доказательство для «примата целостности» - что числа арифметики надо читать целиком.
И я пытаюсь представить, как построить теорию для «квази-строк» - промежуточную между строками и числами арифметики. Чтобы «квази-строки» имели однозначный размер и упорядоченность символов, но чтобы они подчинялись «примату целостности» - когда необходимо прочитать квази-строку целиком, чтобы узнать её часть.
И вот теперь я придумал понятный вариант квази-строки: зашифрованная строка!
Но шифр нужен не «пляшущие человечки», а когда один символ в шифре может изменить весь текст. Именно такие шифры сейчас и используются. И вот если в теории прописать такое «шифрование, то у нас есть квази-строка, у которой есть и размер, и последовательность символов - но это относится к «расшифрованному» тексту. А чтобы узнать расшифрованный текст - надо прочитать весь зашифрованный.
Интересно, что в теории невозможно сформулировать отрицание примата целостности, потому что если расширять теорию в сторону шифрования - то там уже другие объекты, а в рамках исходной теории про них даже невозможно сформулировать утверждения.
Более того, невозможно сформулировать утверждение, что данная теория не описывает логику для расшифрованного текста - потому что в ней нет логики для такой точки зрения. И поэтому любая теория, в которой нет логики примата целостности не может иметь отрицания примата целостности!
Это очень интересный вывод, аналогичный 2-й теореме Гёделя о неполноте. И тут общая природа со 2-ой теоремой Гёделя: она доказала по сути, что теория не может доказать свою отдельность от всего! Ну, противоречивая теория доказывает всё, а доказать, что ты непротиворечива - невозможно. Поэтому невозможно доказать, что ты не являешься всем.
Но из-за этого же, по сути, невозможно доказать и отрицание примата целостности - потому что теория может быть частью другой теории, в которой примат целостности - есть. И его наличие доказано средствами, выходящими за рамки исходной теории. И они не создают противоречий с исходной теорией. Но если при всём при этом противоречие с приматом целостности обнаружилось, то, значит, оно было в исходной теории. Вот поэтому теория с отрицанием примата целостности - противоречива.
Меня очень беспокоил вопрос про отрицание примата целостности, пока я не нашёл данный ответ. Он, конечно, не изложен строго, как 2-я теорема Гёделя, но мне хватило для понимания. А рассуждение тут в любом случае неформальное.
Вывод же такой:
В теории может НЕ быть логики примата целостности. Но при этом для данной теории есть как интерпретации без примата целостности, так и интерпретации с приматом целостности. А вот логика отрицания примата целостности не может быть доказана в теории 1-го порядка, если данная теория непротиворечива.
4. Объёмность вычислений. Да и мыслей тоже :)
Когда я строю модель с лучами данных, то я отправляю по лучам данных пакеты данных. И ячейки имеют типа процессоров, которые обрабатывают сообщения - каждый своё.
Меня смущало, что могут быть вопросы, а не являются ли такие алгоритмы недетерминированными? Но нет, можно построить такой вариант, что каждый момент работает только один узел в Машине, а никаких «тупиковых» вариантов при этом не исключается, просто происходит ненужное замедление. Поэтому это не случай генерации «угадываний», а просто разнесение алгоритма в пространстве - для доставки детерминированных данных.
Подробней я пишу про эту мнимую недетерминированность в работе про модель. И почему надо немного расширить своё понимание «детерминированности». Не бывает такого, чтобы в вычислительной системе вычислял каждый момент только один атом. Вычисление - это объёмный процесс. Как и мышление, кстати. Вот сейчас у меня думает явно не один нейрон. И мысль у меня объёмная. Впрочем, это уже мои субъективные ощущения )
Есть и другие находки, которые поддавались пониманию далеко не сразу. Просто хотел поделиться (скорее даже - сформулировать для себя сводку самого необычного из найденного). Вот тут видно, почему решать математические вопросы - даже довольно практичные, вроде архитектуры модели - требует так много времени. Ты же обдумываешь ещё и вопросы, которые возникают у тебя в теоретическом плане и пытаешься понять, что захотят понять читатели. И я тут не про программистов - практики легко принимают факты. А вот теоретики куда придирчивей - но и знание у них гораздо устойчивей - для чего и устраивается (в том числе) весь этот сыр-бор.
Так что, я сейчас не появляюсь почти в ЖЖ, да и многое другое забросил - пытаюсь концентрироваться на доделывании публикации и сопутствующих вопросов, ответы на которые тоже должны быть готовы для предъявления. Это долго, но я и не рассчитывал на подготовку публикации быстрее, чем за год. Пока ещё до года далеко, да я и продлить могу при необходимости. Аккуратность тут важнее времени.
Ранее по теме:
Капитан Приём, штурман м-р Доза и 1-й помощник м-р Перебор (Аэроплан 2) - 25 октября 2020 г.
Как измерить время "в попугаях" - 24 сентября 2020 г.