Здравствуйте, Sorc17, Вы писали:
DR>>Не все функции вычислимы на машине Тьюринга. Более того, почти все функции невычислимы.
S>Не, есть задачи, для решения которых не существует алгоритма. Вроде даже есть раздел математики, который ими занимается.
Это эквивалентное утверждение. Почти все проблемы неразрешимы по Тьюрингу. Раздел называется theory of computability (часть theoretical computer science).
Здравствуйте, kl, Вы писали:
kl>Здравствуйте, gandjustas, Вы писали:
DR>>>Не все функции вычислимы на машине Тьюринга. Более того, почти все функции невычислимы.
G>>Приведи пример чтоли.
kl>Пример чего? Невычислимой по Тьюрингу функции? Да любая функция, которая принимает на вход инстанс неразрешимой decision problem и выдает результат (да/нет).
Так это невычислимость аргумента, а не функции. Ведь с вычислимым аргументом функция будет вычислимой.
kl>Что касается второй части утверждения Don Reba, то это вполне очевидно: число всех возможных МТ счетно (множество МТ отображается на множество натуральных чисел), в то время как множество функций на вещественных числах, разумеется, несчетно. Отсюда вывод: почти все функции невычислимы. Аналогично: почти все вещественные числа невычислимы и т.д.
Да, потому что вещественные числа точно не представимы в комьютере. При фиксации точности ситуация резко меняется. Опять-таки невычислимый аргумент, а не функция.
Здравствуйте, gandjustas, Вы писали:
DR>>Не все функции вычислимы на машине Тьюринга. Более того, почти все функции невычислимы.
G>Приведи пример чтоли.
Здравствуйте, gandjustas, Вы писали:
G>>>Приведи пример чтоли.
kl>>Пример чего? Невычислимой по Тьюрингу функции? Да любая функция, которая принимает на вход инстанс неразрешимой decision problem и выдает результат (да/нет). G>Так это невычислимость аргумента, а не функции. Ведь с вычислимым аргументом функция будет вычислимой.
Удалил предыдущее сообщение свое, т.к. глупость написал. Если тебе не нравится пример с Kolmogorov complexity, давай рассмотрим тот же busy beaver:
Функция принимает на вход натуральное число (представление некой МТ) и возвращает 0 или 1 в зависимости от того, всегда останавливается n-ая МТ или нет. Где тут невычислимость аргумента? Натуральные числа вычислимы (в строгом смысле вычислимости). А функция невычислима по Тьюрингу.
Здравствуйте, kl, Вы писали:
kl>Здравствуйте, gandjustas, Вы писали:
G>>>>Приведи пример чтоли.
kl>>>Пример чего? Невычислимой по Тьюрингу функции? Да любая функция, которая принимает на вход инстанс неразрешимой decision problem и выдает результат (да/нет). G>>Так это невычислимость аргумента, а не функции. Ведь с вычислимым аргументом функция будет вычислимой.
kl>Удалил предыдущее сообщение свое, т.к. глупость написал. Если тебе не нравится пример с Kolmogorov complexity, давай рассмотрим тот же busy beaver:
kl>Функция принимает на вход натуральное число (представление некой МТ) и возвращает 0 или 1 в зависимости от того, всегда останавливается n-ая МТ или нет. Где тут невычислимость аргумента? Натуральные числа вычислимы (в строгом смысле вычислимости). А функция невычислима по Тьюрингу.
Я верю что есть невычислимые функции, но ты как-то резко в невычислимые записал все.
Само существование профессии программиста говорит об обратном.
Здравствуйте, DarkGray, Вы писали:
DG>В процессоре нет как таковой команды условного перехода.
DG>есть регистр, который отвечает за индекс ячейки содержащей следующую команду. DG>есть автоматическое увеличение этого регистра DG>есть команды, который меняют значение этого регистра DG>есть бесконечный цикл (процессор постоянно пытается выбрать следующую команду и ее выполнить)
Здравствуйте, Don Reba, Вы писали:
DR>Клеточные нейронные сети рекуррентны, то есть они не останавливаются, а приходят в стабильное состояние, если приходят.
Если подавать что-то на вход.. Или выход подать на вход? Но это ж делеко не все НС
Есть несколько доказательств их полноты; одно из них эмулирует game of life, на которой, как известно, можно воспроизвести МТ.
Хотелось бы ссылку. Пока даже представить не могу как оно будет эммулировать.. И что она будет эммулировать.. По моему нет никакой уверенности в том, что она эммулирует.. Есть только надежда что этим можно пользоваться.
Здравствуйте, os24ever, Вы писали:
B>>Вообще говоря необходимо команда условного перехода (ну, кроме присвоения и прибавления 1). Цикл уже конструируется из них.
O>Необязательно. Можно обойтись стеком адресов возврата и командой "снять адрес с вершины стека не двигая её" — и вот он, цикл.
Реализацию здесь не обсуждаем.
Здравствуйте, gandjustas, Вы писали:
kl>>Функция принимает на вход натуральное число (представление некой МТ) и возвращает 0 или 1 в зависимости от того, всегда останавливается n-ая МТ или нет. Где тут невычислимость аргумента? Натуральные числа вычислимы (в строгом смысле вычислимости). А функция невычислима по Тьюрингу.
G>Я верю что есть невычислимые функции, но ты как-то резко в невычислимые записал все.
Не-не-не, я написал *почти* все. Это абсолютно стандартный термин в данном контексте.
G>Само существование профессии программиста говорит об обратном.
Да ладно, "почти все функции невычислимы" совершенно не противоречит утверждению "бесконечное число функций вычислимо", так что на всех программистов хватит =) Для тебя же не секрет, то бесконечные множества вполне можно сравнивать по кардинальности и какие-то из них (невычислимые функции) могут быть больше других (вычислимые функции)?
Здравствуйте, kl, Вы писали:
G>>Само существование профессии программиста говорит об обратном.
kl>Да ладно, "почти все функции невычислимы" совершенно не противоречит утверждению "бесконечное число функций вычислимо", так что на всех программистов хватит =) Для тебя же не секрет, то бесконечные множества вполне можно сравнивать по кардинальности и какие-то из них (невычислимые функции) могут быть больше других (вычислимые функции)?
Теория интересует мало. Ведь многие задачи в общем виде неразрешимы, а частные случаи — вполне. Жизнь — не математика, в жизни нет бесконечно больших и бесконечно малых величин.
Здравствуйте, gandjustas, Вы писали:
G>Да, потому что вещественные числа точно не представимы в комьютере. При фиксации точности ситуация резко меняется. Опять-таки невычислимый аргумент, а не функция.
Вот и функция и число http://en.wikipedia.org/wiki/Chaitin's_constant
Там же и доказательство бесконечности (и большей мощности относительно вычислимых)
множества таких неприводимых чисел.
Здравствуйте, gandjustas, Вы писали:
G>Теория интересует мало. Ведь многие задачи в общем виде неразрешимы, а частные случаи — вполне. Жизнь — не математика, в жизни нет бесконечно больших и бесконечно малых величин.
Когда говорят "почти все" в математическом контексте, то часто имеют в виду все экземпляры, за исключением счётного множества или множества нулевой меры Лебега. Это похоже на то как когда статистики говорят о "значительной" величине, имея в виду всего лишь, что её вероятность достаточно большая, чтобы не быть случайностью.
Здравствуйте, Don Reba, Вы писали:
DR>Здравствуйте, gandjustas, Вы писали:
G>>Теория интересует мало. Ведь многие задачи в общем виде неразрешимы, а частные случаи — вполне. Жизнь — не математика, в жизни нет бесконечно больших и бесконечно малых величин.
DR>Когда говорят "почти все" в математическом контексте, то часто имеют в виду все экземпляры, за исключением счётного множества или множества нулевой меры Лебега. Это похоже на то как когда статистики говорят о "значительной" величине, имея в виду всего лишь, что её вероятность достаточно большая, чтобы не быть случайностью.
Я в курсе что означает "почти все". Вот напримиер почти все действительные числа не представимы в компьютере. Тольеко это не мешает вычислять результаты экспериментов, которые реально не проводятся.
G>IO может в явном виде отсутствовать, просто некоторые ячейки памяти будут замаплены на входы-выходы устройств.
согласен
DG>>зы DG>>В процессоре нет как таковой команды условного перехода. G>Это как? jz\jnz тогда что?
jz/jnz есть макрос, который преобразуется в команды вида:
conditional set ip, x
conditional set ip, ip+x
которая аналогична другим командам присваивания общих регистров:
conditional set ax, x (в masm-е называется cmov)
DG>>есть регистр, который отвечает за индекс ячейки содержащей следующую команду. DG>>есть автоматическое увеличение этого регистра DG>>есть команды, который меняют значение этого регистра DG>>есть бесконечный цикл (процессор постоянно пытается выбрать следующую команду и ее выполнить)
G>Ты с одного уровня абстракции на другой прыгаешь. "команды, который меняют значение этого регистра" (имеется ввиду регистр адреса следующей команды) и есть команды перехода. Так как процессор выполняет все подряд, то нужна команда, которая в зависимости от операндов и состояния вычислителя будет менять или не менять значение регистра следующей команды.
речь до сих пор о минимально необходимом кол-ве команд для построения МТ или о чем-то другом?
неявного внешнего бесконечного for-а, if-а, команд присваивания и команды увеличения/уменьшения на 1 достаточно для построения МТ
внешний-for (;;)
{
if (state == 1)
{
//bla-bla
}
else if (state == ..)
{
//bla-bla
state = x;
}
else // и т.д.
}
DG>>>зы DG>>>В процессоре нет как таковой команды условного перехода. G>>Это как? jz\jnz тогда что?
DG>jz/jnz есть макрос, который преобразуется в команды вида: DG>conditional set ip, x DG>conditional set ip, ip+x
Неверно, jz\jnz — отдельные команды.
DG>которая аналогична другим командам присваивания общих регистров: DG>conditional set ax, x (в masm-е называется cmov)
То есть условность все таки есть, а ты говоришь что нет
DG>речь до сих пор о минимально необходимом кол-ве команд для построения МТ или о чем-то другом?
Если речь о построении МТ, то уже давно доказано сколько и чего нужно. Хоть СПБС, хоть чрф. Не надо выдумывать.
Здравствуйте, Don Reba, Вы писали:
DR>Не все функции вычислимы на машине Тьюринга. Более того, почти все функции невычислимы.
Понятие нейронная сети с вычислимостью как-то не очень согласуется. Вычислимость подразумевает наличие некоторого алгоритма, задающего процесс вычисления данной проблемы. Сама проблема формулируется обычно на бесконечном множестве как области определения, для которых должны быть заданы конкретные значения. Нейронная сеть, как мне кажется (я в этом совсем дилетант), необходима как раз в тех случаях, когда алгоритма не удается сформулировать. В этом случае мы можем попытаться смоделировать алгоритм на данных, которые даны в качестве примера, если, конечно, эти примеры покрывают все множество входных классов значений. Это как раз задача, которая называется "восстановление зависимостей по эмпирическим данным" (название книжки Вапника).
Чуть более абстрактно. Исходная задача: моделирование функции, которая берет на вход бесконечное множество элементов декартова произведения множеств-типов входных параметров и возвращает для них вполне определенные значение в некотором множестве (типа значения). Если входное бесконечное множество удается разбить на конечное множество классов по типу их обработки, то моделирование этого разбиения называется алгоритмом и саму функцию называем вычислимой.
Если такого разбиения произвести нельзя, то это может быть по двум причинам:
1. Такого разбиения вообще нельзя сделать принципиально. Например, нельзя задать алгоритм, берущий на вход последовательность цифр, и определяющий, принадлежит ли эта последовательность записи числа пи после запятой в десятичной системе счисления (говорят, что проблема печати числа пи -- перечислимая, но не разрешимая).
2. Недостаточно знаний для разбиения на классы. В этой ситуации мы можем предположить, что имея какой-то набор (может быть не покрывающий всех классов) входных данных вместе со значениями на них целевой функции, мы можем попытаться восстановить поведение функции на всей области определения.
Наверное, если говорить о вычислимости, как о некоем "рациональном" способе обработки бесконечных данных, то что-то здесь сравнивать можно, и там, и там должно быть разбиение на конечное число классов.
