Такі проблеми виникають практично в усіх розділах математики. В математичній логіці для кожної теорії формулюється проблема розв'язування множини всіх істинних або довідних тверджень цієї теорії відносно множини всіх її пропозиції (теорії поділяються на розв'язні і нерозв'язні в залежності від розв'язності або нерозв'язності вказаної проблеми); у 1936 р. А. Черч встановив нерозв'язність проблеми розв'язності для множини всіх істинних пропозицій логіки предикатів, подальші важливі результати в цьому напрямі належать А. Тарському, А. І. Мальцеву та інші. Нерозв'язні алгоритмічні проблеми зустрічаються в алгебрі (проблема тотожності для напівгруп і, зокрема, для груп; перші приклади напівгруп з нерозв'язною проблемою тотожності були винайдені в 1947 р. незалежно А. А. Марковим і Е. Постом, а приклад групи з нерозв'язною проблемою тотожності — в 1952 р. П. С. Новіковим); в топології (проблема гомеоморфії, нерозв'язність якої для важливого класу випадків була доведена в 1958 р. А. А. Марковим); в теорії чисел (проблема розв'язності діофантових рівнянь, нерозв'язність якої була встановлена в 1970 р. Ю. В. Матіясевичем) та в інших розділах математики.