Дозволи проблема, важливе поняття логіки. Р. п. даної безлічі А конструктивних об'єктів (відносно деякої охоплюючої безлічі V конструктивних об'єктів) називають проблему побудови алгоритму, що розпізнає по всякому об'єкту з безлічі V, чи належить він безлічі А чи ні. Р. п. (детальніше — Р. п. для довідності) формальної системи (або числення ) називається Р. п. безлічі всіх доказових формул цієї системи відносно безлічі всіх її формул. Семантичний Р. п. (або Р. п. для істинності) інтерпретованої формальної системи (формалізованої мови ) називається Р. п. безлічі всіх дійсних формул системи відносно безлічі всіх її формул.
