Какие задачи трудно/невозможно решить вычислительными средствами, но достаточно легко за разумное время человеку с его интуицией?

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

То есть правильность решения легко проверяется формальными средствами, но сложност
решения, даже на современных суперкомпьютерах, такова, что вычисление займет миллио
(допустим) лет без гарантии, что данные вычисления когда-либо кончатся. А решение человеком же хоть и не обязательно легкое, но возможное в разумное время. В качестве примера могу привести, например, задачу по поиску новых типов мозаик из пятиугольников, которую с успехом решила (аж три раза) домохозяйка и математик-любитель Марджори Райс.

Проверить легко может и машина, то есть для проверки правильности человек не нужен:

class AbstractProblemResolver
{
public:
    virtual QByteArray resolve(const QByteArray &problemData) = 0;

    virtual bool check(const QByteArray &solution) const  = 0;
};
//------------------------------------------------------------------
class ConcreteProblemResolver : public AbstractProblemResolver
{
public:
    //выполняется >=1000000 лет без гарантии, что решит
    QByteArray resolve(const QByteArray &problemData) final {
        //TODO: place your code here
    }

    //выполняется меньше, чем за секунду
    bool check(const QByteArray &solution) const final {
        //TODO: place your code here
    }

};

    

Ответы

Ответ 1

Любая задача в первую очередь имеет формулирование. И если формулировка задачи позволяет переложить её на машинный язык, то задача, сможет быть решена машиной. 

По моему мнению, если машина не может этого решить, то было недостаточное для машины формулирование задачи.

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

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

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


Ответ 2

Вам необходимо рассмотреть тему Разрешимое Множество из теории Множеств. Рекоменду
по этой теме поискать книгу Introduction To The Theory Of Computation - Michael Sipser, там этому посвещена отдельная глава.

Сходу так не смогу сказать, но если мне не изменяет память, ТМ в принципе не могу
решать большую часть задач, где данные могут быть бесконечными (например является ли язык А языком, который принимает DFA итд). А ещё придётся прочесть про Computability для понимания.

Конкретнее написать, извините, не могу, т.к. сам понимаю эту тему очень поверхностно
Да, на русском по этой теме в своё время вообще не смог найти никакой информации, а Сипсер пишет относительно доступно.