Джедаи за работой

[andrzejn]

Всякий мало-мальски опытный программист интуитивно чует, способен ли компьютер в принципе справиться с поставленной перед программистом задачей. Я сейчас говорю не об искусственном интеллекте, а о простых повседневных программах.

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

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

Я чую, что из этого следует какой-то важный вывод из области работы разума и построения искусственного интеллекта, но не знаю, какой именно.

Comments

[andrzejn]

Я говорил о более простой вещи: интуитивном чутье алгоритмизируемости (как правильно подсказал gds в соседнем комменте). Сможет ли программист реализовать принципиально возможный алгоритм, правильно ли он оформит вызовы пользователя - это отдельный вопрос. Но если нет этого интуитивного чутья "стоит ли вовсе программировать эту задачу", то это определённо плохой, негодный программист.

Что же до судов и Монолита, я не вижу здесь проблемы. Как справедливо сказано по той ссылке, легальные вопросы решаются отнюдь не формальной логикой, и от логики они весьма далеки. Просто другая область.

[faceted-jacinth.livejournal.com]

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

Вот у Аввы недавно было (http://avva.livejournal.com/1994683.html), в комменты не смотрите, там есть решения. Переформулирую для краткости, есть три типа машин тьюринга:
1) Либо останавливается, либо входит в цикл (состояние ленты и машины повторяется периодически).
2) Либо останавливается, либо входит в цикл (состояние машины и текущий символ повторяются периодически).
3) Либо останавливается, либо входит в цикл (состояние машины повторяется периодически).
Определить, какой класс языков распознают каждый из девайсов.

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

Да, более практический пример: decidablility of java type system is currently unknown. То есть пока непонятно, можно ли написать компилятор, который для любых двух сложных типов корректно ответит, является ли один сабтайпом другого.

[andrzejn]

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

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

Это примеры чистого чутья: с обеими областями я знаком чересчур поверхностно.