Квадратура овала наповал

[fregimus]

На веб-сайте getacoder.com можно найти бизнес-партнера для разработки программы по спецификации. И вот что там было предложено сегодня:

Заказчик: Алан Т.

Проект: отладчик.

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

А вот какие интересныв предложения уже получил Алан Т.

sabasak, Манама, Бахрейн: $2000, 10 дней. Спецификация ясна, готов начать.

victorbd, Мадрас, Индия: $550, 10 дней. Глубокоуважаемый Алан Т., Мы готовы начать ваш Проект нашей превосходной командой программистов, Разработчиков и Управляющих Проектами. Мы на 100% уверены для успешного исполнения вашего Проекта. Мы оказываем Услуги многим Большим Клиентам на Всем Земном Шаре & надеемся на Превосходные и Долгие Деловые Отношения с вашей Досточтимой Организацией. Пожалуйста, Проверьте почту — мы отправили Реквизиты и Наш Портфолио. С глубоким уважением

ISTM84, София, Болгария: $300, 15 дней. Предлагоаем сделать за $300 и 15 дней.

germanquality, Франкфурт, Германия: $300, 1 день. Будучи превосходным немецким программистом, я уже решил задачу из вашей спецификации. Могу закодировать решение на любом языке, позволяющем напечатать строку текста. Если требуется, могу также предоставить блок-схему и решение на качественной бумаге немецкого производства.

BusyBeaver, Лодзь, Великобритания: $1729, 1 день. Решу вашу задачу так продуктивно, как только возможно.

Отметились также Курт Гедель (KurtG) и Георг Кантор (GeorgeCantor).

Тем, кто подзабыл исторический материализм, напомню: сформулированная задача — классическая неразрешимая задача вычислительной математики. Алан Тьюринг доказал в 1936 г., что такой «отладчик» невозможен. Это предложение выглядит, как если бы математикам предложили предложили решить задачу квадратуры круга — ну-ка, кто поменьше запросит и побыстрее решит?

Предложения принимаются в течение 30 дней. Клоунада продолжается, так что ждем новых замечательных обещаний решить эту задачу — пуще прежних!

Comments

[arno1251.livejournal.com]

Темой моей дипломной работы была программа (PL/1), вносящая в другую программу (Fortran-77) ошибки, не регистрируемые компилятором. Я искренне полагал, что более дурацкий проект придумать невозможно...

[fregimus.livejournal.com]

А если чтобы она делала то же самое, но в рифму?

[arno1251.livejournal.com]

:)

[timur0.livejournal.com]

>>решение на качественной бумаге немецкого производства

Этот явно догадался

[fregimus.livejournal.com]

Читал, много думал. Ох, не уверен…

[nazarovsky.livejournal.com]

супер!

[livius.livejournal.com]

Построение правильного семиугольника:
http://livius.livejournal.com/41778.html

[bvn-mai.livejournal.com]

Огромное спасибо :), у нас вся фирма легла под стол

[avva.livejournal.com]

Неряшливость условия ("бесконечный цикл") дает удобный случай задуматься. Что такое бесконечный цикл в контексте машины Тьюринга, и можно ли сказать, что любая неостанавливающаяся машина входит в него? Может ли быть, что вхождение в бесконечный цикл, в отличие от неостановки, можно распознать?

[yaguanodont.livejournal.com]

:)

Почему нет?

[cmike.livejournal.com]

Готов решить задачу, если мне предоставят компьютер. Разумеется, необходимо, чтобы каждый следующий такт этим компьютером должен выполняться не менее чем на 8% быстрее предыдущего.Г

Re: Почему нет?

[ivan-gandhi.livejournal.com]

А закон Мура не годится в качестве подспорья?

[http://users.livejournal.com/_nik_/]

Что-то не вижу там больше ни одного бида, зато вижу в MB раскрытие темы.

Проблема разрешимости

[(Anonymous)]

Неразрешима проблема для машины с БЕСКОНЕЧНОЙ памятью

На фрилансерских сайтах пишут проги для машин с конечной памятью. А в условиях задачи явно не оговаривается.
Для такой машины все просто:
пусть память машины N бит (именно память а не разрядность), то есть для типового компа скажем 2^32

запускаем эту прогу в эмуляторе машишы и ждем 2^N шагов (2^(2^32) для нашего примера) , если прога не завершился -значит она зациклилась - вот и ответ.

Ключевое различме с машиной тьюринга - у той бесконечная память потому завершения можно не дождаться

P.S.
где можно получить 5 копеек за решение?:)

Re: Проблема разрешимости

[fregimus.livejournal.com]

запускаем эту прогу в эмуляторе машишы и ждем 2^N шагов (2^(2^32) для нашего примера)
Если машина делает, скажем, 17 миллиардов операций в секунду (2^34), то ждать будем 2^(2^32-34) секунд. Это примерно 2^(2^32-59) лет. Это, конечно, меньше, чем 2^2^32 лет, но, я бы сказал, несущественно меньше. Это так — по поводу конечного времени.

где можно получить 5 копеек за решение?
Как досчитает до конца — так сразу и получите. Придется, правда, подождать — зато какой процент набежит!

Re: Проблема разрешимости

[janatem.livejournal.com]

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

[cousin-it.livejournal.com]

BusyBeaver это тоже шутка, как гедель и кантор

[fregimus.livejournal.com]

Ну да, странная только какая-то. Радо был венгр — почему Лодзь, Великобритания? И еще говорили, будто он был начисто лишен чувства юмора…

[avva.livejournal.com]

Великобритания - потому что оттуда Харди; Харди, потому что $1729; $1729 - потому что история про Харди и Рамануджана.
Почему Лодзь - не знаю :)

[fregimus.livejournal.com]

А почему Харди и Рамануджан?

[avva.livejournal.com]

Вот здесь хорошо объяснено:

http://en.wikipedia.org/wiki/1729_(number)

[fregimus.livejournal.com]

То есть, я правильно понял — просто одно из знаменитых 42, и никакой несопредственной связи с задачей? Или я никак не въеду, и тут есть связь?

[avva.livejournal.com]

Да, просто знаменитое число, связи с проблемой остановки никакой.

[fregimus.livejournal.com]

З. Ы. На вашу запись про МТ я молчу, но не потому, что я невежливый, а потому что я ее думаю.

[snt.livejournal.com]

шедеврально.
жаль только, что оригинальная страница на getacoder.com не сохранилась.