В computer science есть доказанные теоремы разумеется, странно слышать обратное.

> Контрфактуальность в формулировках теории вполне вычислима

Именно в формулировках? Вычислима в смысле мы можем алгоритмически "посмотреть" на формулы и понять, присутствуют там контрфактуальные утверждения или нет? При наличии формальной нотации для выражения причинности и контрфактуальности? Ну, прям Америку открыли, супер удивительный результат! 😊

Только всё тот же Джудиа Пирл указывает, что проверить-то можно, и не только наличие в формулах, но и соответствие "реальности" при наличии достаточного количества данных. Однако. Чтобы вообще сформулировать (записать формально) суждения о причинности (не говоря про контрфактуальность) нужна априорная модель, которую статистически из данных "вытащить" невозможно — нужно как-то "придумать" и "спустить сверху".

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

Я вполне допускаю, что "модель вычислима" в конечном итоге, но пока это вилами по воде писано. 🤷‍♀️

Вообще первый абзац вызывает скорее недоумение, это не просто не очевидно, это вроде бы просто неверно. А верно следующее, если существует хотя бы одна функция обладающая свойством Х, и хотя бы одна функция не обладающая свойством Х, то задача "обладает ли свойством Х данная функция f" невычислима в общем случае. Так что свойство  "содержать контрфактуальные утверждения" тоже не должно быть вычислимо. Если я вас неправильно понял поправьте пожалуйста.

Да, всё именно так, и "априорная модель" в конечном итоге и вытаскивается из шума, а не "порождается детерминистским алгоритмом" (закономерности, как что-то осмысленное может быть вытащено из шума изучают эволюционные алгоритмики — Stanley и прочие из open-endedness движения).

А модели можно брать из списка всех всех возможных программ, почему нет.

Не совсем так. Байес там на нижней ступеньке: он помогает выбрать между несколькими вариантами объяснений, а сами объяснения надо породить/generate откуда-то, они даются через guess (догадку), а не выводятся из статистики, а хоть и байесовской.

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

Это не теоретическая проблема. На вопрос "а где взять гипотезы" это нормальный ответ, то что он не практичный не страшно, допилим.

Я так понял, Вы ссылаетесь на теорему Райса?

Я не говорил про произвольные нетривиальные свойства произвольных функций. Я имел в виду определённое синтаксическое свойство некоторой формальной теории — такой, в которой существует нотация для понятия причинности и контрфактуальных утверждений соответственно. Понятно, что такая теория может быть и неразрешимой, но может быть и полностью разрешимой, или хотя бы полуразрешимой.

Может я ошибаюсь, но там не получится так, что чтобы эта формальная теория была достаточно выразительной ей придётся быть неразрешимой?

Как минимум — долго! 🤣

Вообще, если брать Judea Pearl's do-calculus, то там модели — конкретно причинных связей — представлены в виде (ненаправленного) графа, так что "все возможные программы" — вообще слишком широкая область для поиска таких графов. 😊

Не знаю — надо изучать! 😃

Я либо не понимаю, что значит "вытаскиваются из шума", либо не верю в это. Но Вы тут сами упёрлись в невычислимость в смысле МТ ("честный" рандом невычислим). 🤷‍♀️

Учитывая что эти графы хоть и направленные и ациклические, но ненаправленные циклы в них быть могут, и что корреляции могут расходиться  не только в направлении стрелок причинности я не уверен сходу что там нельзя такой граф как нибудь достаточно хитро составить чтобы получилась универсальная вычислительная штука. Интуитивно конечно кажется что нельзя, но мало ли.

Я то как раз за физичность вычисления топлю. И за системность (в состав моего физического вычислителя вполне может входить тепловой генератор случайных чисел). Что касается математической вычислимости, то computer science как раз про то, что там вообще из математики может быть вычислимо на физических вычислителях, а что нет (и это вроде как экспериментальная наука, чистой логикой это не берётся, для объяснений тут нужны догадки, которые опять-таки берутся "из шума").

Тут квантовые компьютеры и как доказывается, что они универсальные по Тьюрингу — вот сюда ещё нужно смотреть. Computer science как раз про компьютеры как физические девайсы, а не про математические девайсы. Про математические девайсы самой математики хватает, не нужно другой науки.

Про физические девайсы самой физики хватает, не нужно другой науки.

Физика не обсуждает, как физические девайсы отражают поведение математических/идеальных объектов. Физика про поведение физических девайсов как таковое. Математика про поведение математических объектов. Computer science — про correspondence rules между ними.

CS в части теории вычислимости — про машину Тьюринга, а не про физические машины/вычислители. Остальная CS — ещё больше "про математику" (хотя куда уж больше?).

Про физические вычислительные машины и комплексы — это к Electrical Engineering.

Звучит как пустое определение которое ничего не обозначает.

Приведите если можно пример вопроса который не относится ни к физике ни к математике но относится к computer science.