?

Log in

No account? Create an account

Previous Entry | Next Entry

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

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

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

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

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

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

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

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

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

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

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

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

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

Tags:

Comments

( 25 comments — Leave a comment )
arno1251
Nov. 26th, 2008 09:31 am (UTC)
Темой моей дипломной работы была программа (PL/1), вносящая в другую программу (Fortran-77) ошибки, не регистрируемые компилятором. Я искренне полагал, что более дурацкий проект придумать невозможно...
fregimus
Nov. 26th, 2008 10:16 am (UTC)
А если чтобы она делала то же самое, но в рифму?
arno1251
Nov. 26th, 2008 11:14 am (UTC)
:)
timur0
Nov. 26th, 2008 10:10 am (UTC)
>>решение на качественной бумаге немецкого производства

Этот явно догадался
fregimus
Nov. 26th, 2008 10:17 am (UTC)
Читал, много думал. Ох, не уверен…
nazarovsky
Nov. 26th, 2008 10:11 am (UTC)
супер!
livius
Nov. 26th, 2008 11:17 am (UTC)
Построение правильного семиугольника:
http://livius.livejournal.com/41778.html
bvn_mai
Nov. 26th, 2008 11:34 am (UTC)
Огромное спасибо :), у нас вся фирма легла под стол
avva
Nov. 26th, 2008 11:37 am (UTC)
Неряшливость условия ("бесконечный цикл") дает удобный случай задуматься. Что такое бесконечный цикл в контексте машины Тьюринга, и можно ли сказать, что любая неостанавливающаяся машина входит в него? Может ли быть, что вхождение в бесконечный цикл, в отличие от неостановки, можно распознать?
yaguanodont
Nov. 26th, 2008 01:21 pm (UTC)
:)
cmike
Nov. 26th, 2008 03:17 pm (UTC)
Почему нет?
Готов решить задачу, если мне предоставят компьютер. Разумеется, необходимо, чтобы каждый следующий такт этим компьютером должен выполняться не менее чем на 8% быстрее предыдущего.Г
juan_gandhi
Nov. 26th, 2008 06:26 pm (UTC)
Re: Почему нет?
А закон Мура не годится в качестве подспорья?
_nik_
Nov. 26th, 2008 07:11 pm (UTC)
Что-то не вижу там больше ни одного бида, зато вижу в MB раскрытие темы.
(Anonymous)
Nov. 26th, 2008 09:03 pm (UTC)
Проблема разрешимости
Неразрешима проблема для машины с БЕСКОНЕЧНОЙ памятью

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

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

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

P.S.
где можно получить 5 копеек за решение?:)
fregimus
Nov. 27th, 2008 01:01 am (UTC)
Re: Проблема разрешимости
запускаем эту прогу в эмуляторе машишы и ждем 2^N шагов (2^(2^32) для нашего примера)
Если машина делает, скажем, 17 миллиардов операций в секунду (2^34), то ждать будем 2^(2^32-34) секунд. Это примерно 2^(2^32-59) лет. Это, конечно, меньше, чем 2^2^32 лет, но, я бы сказал, несущественно меньше. Это так — по поводу конечного времени.

где можно получить 5 копеек за решение?
Как досчитает до конца — так сразу и получите. Придется, правда, подождать — зато какой процент набежит!
janatem
Nov. 27th, 2008 09:31 am (UTC)
Re: Проблема разрешимости
Кроме того, такое (теоретически) проходит только для программ, которые не читают (бесконечно много) данных с внешних устройств.
cousin_it
Nov. 29th, 2008 09:31 am (UTC)
BusyBeaver это тоже шутка, как гедель и кантор
fregimus
Nov. 29th, 2008 09:42 am (UTC)
Ну да, странная только какая-то. Радо был венгр — почему Лодзь, Великобритания? И еще говорили, будто он был начисто лишен чувства юмора…
avva
Nov. 30th, 2008 01:07 pm (UTC)
Великобритания - потому что оттуда Харди; Харди, потому что $1729; $1729 - потому что история про Харди и Рамануджана.
Почему Лодзь - не знаю :)
fregimus
Nov. 30th, 2008 09:35 pm (UTC)
А почему Харди и Рамануджан?
avva
Nov. 30th, 2008 10:09 pm (UTC)
Вот здесь хорошо объяснено:

http://en.wikipedia.org/wiki/1729_(number)
fregimus
Nov. 30th, 2008 10:39 pm (UTC)
То есть, я правильно понял — просто одно из знаменитых 42, и никакой несопредственной связи с задачей? Или я никак не въеду, и тут есть связь?
avva
Nov. 30th, 2008 10:44 pm (UTC)
Да, просто знаменитое число, связи с проблемой остановки никакой.
fregimus
Nov. 30th, 2008 09:44 pm (UTC)
З. Ы. На вашу запись про МТ я молчу, но не потому, что я невежливый, а потому что я ее думаю.
snt
Jun. 9th, 2009 03:27 am (UTC)
шедеврально.
жаль только, что оригинальная страница на getacoder.com не сохранилась.
( 25 comments — Leave a comment )