Здравствуйте, GhostCoders, Вы писали:

GC>Поэтому АНАЛИЗАТОР должен иметь O( 2^(256*8*1024)*10 ) бит данных для анализа

Это называется приплыли.

Здравствуйте, ., Вы писали:

>> Т.е. ты говоришь, что есть формулы, которые записываются не языком, а
>> чем-то ещё?
>> Приведи пример.
.>Нет, проблема в том, что ты не можешь создать 1 такой язык, который будет описывать все возможные формулы.
Прикольный момент в том, что для любого не более чем счётного подмножества действительных чисел можно придумать формальный язык (тебя наверное это и ввело в заблуждение), их даже можно объединять кучами (опять же счётными), но всё сразу объеденить невозможно, оставшись в рамках "finite strings of letters".

Здравствуйте, GhostCoders, Вы писали:

GC>Здравствуйте, Voblin, Вы писали:

V>>Здравствуйте, GhostCoders, Вы писали:

GC>>> Хочется сказать, что многие программисты, изучая в институте машину Тьюринга,
GC>>> конечно слышили о проблеме неразрешимости, так же как и о "вечном двигателе" и попытках создать его.
GC>>> Но есть одно НО, машина Тьюринга бесконечна, для конечных машин, проблема зависания все же
GC>>> РАЗРЕШИМА, хотя бы в теории. Про это обычно забывают, и в английской вики про это пишут,
GC>>> что это распространенное заблуждение, что неразрешимость проблемы машины Тьюринга переносят
GC>>> на конечные компьютеры. http://en.wikipedia.org/wiki/Halting_problem — сомтрите "Common pitfalls".

V>>Не знаю, что там где пишут, но если посмотреть на доказательство теоремы про неразрешимость проблемы останова, то там про бесконечность машины ничего не сказано. Просто оказывается не очень сложно сконструировать такие исходные данные для "универсального решателя проблемы останова", при которых и ответ "да", и ответ "нет" оказываются неправильными. Типа парадокса брадобрея.

GC>Это меня и настрораживает. Мне кажется, что парадокс брадобрея можно применить и к другим объектам, да к чем угодно!
GC>Замените, свого "алгоритм" в доказательстве Тьюринга любым другими словом и понятием и получается, что мы прийдем к такому же результату!

получается что Алан Тьюринг доказал что брадобреев в природе не сущсетвует.

попустим, ты скажешь, "обязуюсь брить тех и только тех кто не бреет сам себя"...
так тебя значить в природе не может быть по теории Тьюринга!!! Ты оказываешься пустое место! Тебе нема!

Здравствуйте, GhostCoders, Вы писали:

GC>Поэтому АНАЛИЗАТОР должен иметь O( 2^(256*8*1024)*10 ) бит данных для анализа

В какой-какой степени 2?
256 * 8 * 1024 == 2097152! Знаете, что pow из Python думает об этом? Она думает:

>>> pow ( 2, 2097152 )
Traceback (most recent call last):
File "<pyshell#3>", line 1, in <module>
pow ( 2, 2097152 )
OverflowError: math range error

Даже WinNTL (библиотека для работы с большими числами) достаточно долго (где-то с минуту) думает...
О! Есть результат. Приводить сюда не буду, потому что запись числа занимает 631 306 десятичных цифр!
Это и называют "стремится к бесконечности".

Здравствуйте, GhostCoders, Вы писали:

GC>получается что Алан Тьюринг доказал что брадобреев в природе не сущсетвует.

GC>попустим, ты скажешь, "обязуюсь брить тех и только тех кто не бреет сам себя"...
GC>так тебя значить в природе не может быть по теории Тьюринга!!! Ты оказываешься пустое место! Тебе нема!

Скажем я заявлю подобное: "обязуюсь брить тех и только тех кто не бреет сам себя"

С точки доказательства Тьюринга меня в природе не может быть... но я есть и пишу сообщения в этом форум

Здравствуйте, GhostCoders, Вы писали:

GC>попустим, ты скажешь, "обязуюсь брить тех и только тех кто не бреет сам себя"...
GC>так тебя значить в природе не может быть по теории Тьюринга!!! Ты оказываешься пустое место! Тебе нема!
Товарищ ".", у тебя там нет под рукой учебника проф. Непейводы, чтобы оттуда привести цитату про философские выводы из теоремы Геделя о неполноте?

Здравствуйте, GhostCoders, Вы писали:

GC>Это меня и настрораживает. Мне кажется, что парадокс брадобрея можно применить и к другим объектам, да к чем угодно!
Называется это "парадокс Рассела" и это всего-навсего показывает, что наивная теория множеств — противоречива.

GC>Замените, свого "алгоритм" в доказательстве Тьюринга любым другими словом и понятием и получается, что мы прийдем к такому же результату!
Нет.

Здравствуйте, FR, Вы писали:

C>>Все существующие и планируемые системы квантовых компьютеров — равномощны МТ и могут быть симулированы на обычном компьютере.
FR>Мне казалось что нет, наверно склероз подвел, или воздейcтвие Пенроуза
Вообще-то, да.

FR>А вообще для практики не нужен квантовый компьютре достаточно аппаратной недетерминированной машины Тьюринга, вообще хватает вызова всего одной функции, любимой схемерами функции Amb
На практике квантовые компьютеры позволяют уменьшить класс сложности для многих задач.

Здравствуйте, Cyberax, Вы писали:

FR>>А вообще для практики не нужен квантовый компьютре достаточно аппаратной недетерминированной машины Тьюринга, вообще хватает вызова всего одной функции, любимой схемерами функции Amb
C>На практике квантовые компьютеры позволяют уменьшить класс сложности для многих задач.

Так Amb тоже сводит NP-полные алгоритмы к полиномиальным.

Здравствуйте, GhostCoders, Вы писали:

GC>Это меня и настрораживает. Мне кажется, что парадокс брадобрея можно применить и к другим объектам, да к чем угодно!
Например?

GC>Замените, свого "алгоритм" в доказательстве Тьюринга любым другими словом и понятием и получается, что мы прийдем к такому же результату!
Тем не менее, доказательство получается вполне строгим. Но это не должно тебя шокировать. Задачки с ответами "ни да, ни нет" и "и да, и нет" — довольно экзотическая штука, и от них всегда попахивает некоторой искусственностью и надуманностью.

Здравствуйте, Voblin, Вы писали:

V>Здравствуйте, GhostCoders, Вы писали:

GC>>Это меня и настрораживает. Мне кажется, что парадокс брадобрея можно применить и к другим объектам, да к чем угодно!
V>Например?

GC>>Замените, свого "алгоритм" в доказательстве Тьюринга любым другими словом и понятием и получается, что мы прийдем к такому же результату!
V>Тем не менее, доказательство получается вполне строгим. Но это не должно тебя шокировать. Задачки с ответами "ни да, ни нет" и "и да, и нет" — довольно экзотическая штука, и от них всегда попахивает некоторой искусственностью и надуманностью.

Не знаю. Заменим в суждениях Тьюринга слово "машина Тьюринга" понятием обычная легковая машина.
Выполнять алгоритм — "ездить".

Получается что не сущвествует легковой машины, которая могла бы возить лругие легковые машины???

Здравствуйте, GhostCoders, Вы писали:

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

Здравствуйте, mrTwister, Вы писали:

T>Таким подходом можно решить задачу века: заставить компьютер писать программы вместо человека. Для этого всего лишь надо перебирать последовательности байт, рано или поздно мы гарантированно получим программу, которая делает то, что нам нужно.

Да что там века!
Все помнят, что бесконечное количество обезьян за пишущими машинками когда-нибудь повторят "Гамлета" ?
Тогда и писатели будут не нужны

Здравствуйте, GhostCoders, Вы писали:

GC>Не знаю. Заменим в суждениях Тьюринга слово "машина Тьюринга" понятием обычная легковая машина.
GC>Выполнять алгоритм — "ездить".
Заменим слово "алгоритм" на "берёза", а "машина Тьюринга" на "Луна".

"Получается, что не существует берёзы, которая могла бы определить останавливается ли Луна".

Здравствуйте, Cyberax, Вы писали:

C>Здравствуйте, GhostCoders, Вы писали:

GC>>Не знаю. Заменим в суждениях Тьюринга слово "машина Тьюринга" понятием обычная легковая машина.
GC>>Выполнять алгоритм — "ездить".
C>Заменим слово "алгоритм" на "берёза", а "машина Тьюринга" на "Луна".

C>"Получается, что не существует берёзы, которая могла бы определить останавливается ли Луна".
ну вот я тоже к этому пришел.

Здравствуйте, GhostCoders, Вы писали:

C>>Заменим слово "алгоритм" на "берёза", а "машина Тьюринга" на "Луна".
C>>"Получается, что не существует берёзы, которая могла бы определить останавливается ли Луна".
GC>ну вот я тоже к этому пришел.
Стоит понимать, что математические выражения являются верными не потому, что "звучат" правильно, а потому, что они выводятся из изначальных аксиом в данной теории.

Т.е. имеем аксиомы:
1. Рыбы летают.
2. Полосатые рыбы опыляют цветы.
3. Есть хотя бы одна полосатая рыба.
В этой теории у нас будет верно выражение: "Есть рыбы, опыляющие цветы". Хотя звучит оно как полный бред.

В общем, рекомендую почитать учебник по мат. логике.

Здравствуйте, GhostCoders, Вы писали:

GC>Здравствуйте, Аноним, Вы писали:

А>>Здравствуйте, GhostCoders, Вы писали:

GC>>>Здравствуйте, D. Mon, Вы писали:

DM>>>>Здравствуйте, GhostCoders, Вы писали:

GC>>>>>Реализовал транслятор простейшего языка программирования.

DM>>>>Очень хорошо. Теперь нужно перевести на этот язык вот эту простейшую функцию:
DM>>>>http://rsdn.ru/forum/Default.aspx?mid=3307978

Автор: RomikT
Дата: 27.02.09

DM>>>>и узнать, наконец-то ответ!

GC>>>Вот пример данной функции на этом языке:

GC>>>* This is function from RomikT *

GC>>>PROGRAM RomikT
GC>>>INPUT n TYPE int8

А>>Как бы так помягче выразиться.. С какого перепугу N тут int8? "Анализатор" тупо перебирает все возможные значения входных параметров??

GC>А почему бы и нет?

Потомучто видимо это может длиться несколько лет в некоторых случаях.

Здравствуйте, C0x, Вы писали:

GC>>А почему бы и нет?

C0x>Потомучто видимо это может длиться несколько лет в некоторых случаях.

Угу солнце как раз к этому времени перейдет в стадию красного гиганта

Здравствуйте, FR, Вы писали:

C0x>>Потомучто видимо это может длиться несколько лет в некоторых случаях.
FR>Угу солнце как раз к этому времени перейдет в стадию красного гиганта
Шнайер оценивал, что для идеального компьютера потребуется примерно энергия взрыва сверхновой, чтобы перебрать 2^220 бит. Так что просто энергии вряд ли хватит

Здравствуйте, Cyberax, Вы писали:

C>Шнайер оценивал, что для идеального компьютера потребуется примерно энергия взрыва сверхновой, чтобы перебрать 2^220 бит. Так что просто энергии вряд ли хватит

Фейнман вроде доказал что обратимые вычисления возможны без затрат энергии вообще. Правда кажется что такие вычислители не Тьюринг-полные.