andrzejn: (Curious)
Андрій Новосьолов ([personal profile] andrzejn) wrote2008-12-26 05:10 pm

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

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

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

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

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

[identity profile] faceted-jacinth.livejournal.com 2008-12-26 07:50 pm (UTC)(link)
Категорически не соглашусь!

Хотя, может, я не так понял, конечно.

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

Во-вторых, хотя это может быть и из субъективного опыта выведено и не относится напрямую к делу, многие программисты крайне фигово понимают, какие вещи на самом деле следует оставить людям. Например, представляя суд как эдакий алгоритм, исходящий из презумции невиновности и принимающий исключительно строгие (в математическом смысле) доказательства, такой воображаемый суд должен был бы оправдать и Ханса Рейзера, и гипотетического чувака, использующего Monolith (http://monolith.sourceforge.net/) (вот весьма поучительная ссылка (http://ansuz.sooke.bc.ca/lawpoli/colour/2004061001.php), объясняющая, в чём проблема, и даже я первый раз читая этот текст был настроен крайне скептически, пока автор не использовал свой Последний Довод).

А что вы имели в виду на самом деле, если я не так понял?

[identity profile] faceted-jacinth.livejournal.com 2008-12-27 11:04 am (UTC)(link)
Хм, но если вы говорите именно о формальной алгоритмизуемости, то есть грубо говоря о наличии у программиста в голове детектора тьюринг-полных языков (точнее, языков с undecidable проблемой останова, не уверен, что это одно и то же), то это тоже в общем-то кажется правдой только пока имеешь дело с простыми алгоритмизируемыми задачами =)

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

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

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