Вопросы с тегом «combinatory-logic»

26
Являются ли лямбда-исчисление и комбинаторная логика одинаковыми?

В настоящее время я читаю « Лямбда-исчисление и комбинаторы » Хиндли и Селдина. Я не эксперт, но всегда интересовался лямбда-исчислением из-за участия в функциональном программировании (начиная с Lisp и SICP, а теперь с R и Haskell). В « Binary лямбда - исчисления и комбинаторной логики» , Джон...

combinatory-logic functional-programming lambda-calculus
20
Краткая схема представления графов

Класс сложности PPAD (например, вычисление различных равновесий по Нэшу) может быть определен как совокупность полных задач поиска, многократно сводимых к END OF LINE : КОНЕЦ ЛИНИИ : Для заданных схем S и P с n входными битами и n выходными битами, такими что P (0 n ) = 0 n ! = S (0 n ) , найти...

reference-request combinatory-logic graph-theory ppad
18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

computability computing-over-reals lambda-calculus graph-theory co.combinatorics cc.complexity-theory reference-request graph-theory proofs np-complete cc.complexity-theory machine-learning boolean-functions combinatory-logic boolean-formulas reference-request approximation-algorithms optimization cc.complexity-theory co.combinatorics permutations cc.complexity-theory cc.complexity-theory ai.artificial-intel p-vs-np relativization co.combinatorics permutations ds.algorithms algebra automata-theory dfa lo.logic temporal-logic linear-temporal-logic circuit-complexity lower-bounds permanent arithmetic-circuits determinant dc.parallel-comp asymptotics ds.algorithms graph-theory planar-graphs physics max-flow max-flow-min-cut fl.formal-languages automata-theory finite-model-theory dfa language-design soft-question machine-learning linear-algebra db.databases arithmetic-circuits ds.algorithms machine-learning ds.data-structures tree soft-question security project-topic approximation-algorithms linear-programming primal-dual reference-request graph-theory graph-algorithms cr.crypto-security quantum-computing gr.group-theory graph-theory time-complexity lower-bounds matrices sorting asymptotics approximation-algorithms linear-algebra matrices max-cut graph-theory graph-algorithms time-complexity circuit-complexity regular-language graph-algorithms approximation-algorithms set-cover clique graph-theory graph-algorithms approximation-algorithms clustering partition-problem time-complexity turing-machines term-rewriting-systems cc.complexity-theory time-complexity nondeterminism
17
Наименьший возможный универсальный комбинатор

Я ищу наименьший возможный универсальный комбинатор , измеряемый количеством абстракций и приложений, необходимых для указания такого комбинатора в лямбда-исчислении . Примеры универсальных комбинаторов включают в себя: размер 23: λf.f (fS (KKKI)) K размер 18: λf.f (fS (KK)) K размер 14: λf.fKSK...

lo.logic computability lambda-calculus universal-computation combinatory-logic
14
Как можно превратить бесконечные

Я думал об этих вопросах: Существует ли типизированное лямбда-исчисление, которое является последовательным и полным по Тьюрингу? /cs/65003/if-%CE%BB-xxx-has-a-type-then-is-the-type-system-inconsistent и уже нет трудно ответить на связанные вопросы в нетипизированной обстановке! В частности, мне...

lambda-calculus combinatory-logic
10
Неполная основа комбинаторов

Это вдохновлено этим вопросом. Пусть будет совокупностью всех комбинаторов, которые имеют только две связанные переменные. Является ли C комбинаторно полным?СC\mathcal{C}СC\mathcal{C} Я считаю, что ответ отрицательный, однако я не смог найти ссылку для этого. Я также был бы заинтересован в ссылках...

lo.logic lambda-calculus combinatory-logic
10
На какой «вопрос» пытается ответить теория языка программирования?

Я давно интересовался различными темами, такими как комбинаторная логика, лямбда-исчисление, функциональное программирование, и изучал их. Однако, в отличие от «Теории вычислений», которая стремится ответить на вопрос «вычислимости», то есть вещей, которые могут / не могут быть вычислены с...

soft-question pl.programming-languages lambda-calculus big-picture combinatory-logic