Siksha Sarovar

Siksha Sarovar (sikshasarovar.com) is a free educational web application that helps students in India learn programming and prepare for academic and competitive exams. The platform offers structured coding courses (C, C++, Python, Java, HTML, CSS, PHP, Power BI, AI, Machine Learning, Data Science), complete university curriculum notes for BCA/MCA students with previous year question papers, Class 10 and Class 12 CBSE/HBSE school notes, and dedicated preparation material for SSC, UPSC, Banking, Railway and other government exams. Browsing the site is completely free and requires no account. Users may optionally sign in with Google solely to save their learning progress, quiz scores and personal preferences across devices.

Privacy Policy | Terms of Service | Contact Siksha Sarovar | About Siksha Sarovar

v4.0.9 · PWA
Siksha Sarovar logo
Siksha Sarovar
Your Learning Universe

Siksha Sarovar is a free e-learning platform for coding courses, BCA university notes and competitive exam preparation. Optional Google sign-in saves your learning progress across devices.

Initializing knowledge base…
Compiling modules 0%

Unit 2 — Computable Functions and Predicates

Lesson 20 of 34 in the free Artificial Intelligence notes on Siksha Sarovar, written by Rohit Jangra.

Computable Functions and Predicates

Predicate logic becomes genuinely useful to a computer program only when its predicates and functions can be evaluated or proven — this is where the ideas of computable functions and computable predicates come in.

Functions vs Predicates

FunctionPredicate
ReturnsAn object (a value)A truth value (true/false)
ExampleFatherOf(Ram) returns DashrathStudent(Ram) returns true
Notationf(x)P(x)

A predicate can be thought of as a special case of a function whose output is restricted to {True, False}.

Computable Functions

A function is computable if there exists an effective procedure (an algorithm that always terminates) to compute its output for any valid input. Most functions used in AI knowledge bases — arithmetic functions, string operations, list operations — are computable in this sense.

Plus(2, 3) = 5
FatherOf(Ram) = Dashrath
Length([a, b, c]) = 3

Computable Predicates

A predicate is computable (also called decidable) if there is an algorithm that, given any input, always halts and correctly outputs True or False.

PredicateComputable?Why
Even(n) — is n even?YesSimple modulus check, always halts
GreaterThan(x, y)YesDirect numeric comparison
Provable(phi) in full first-order logic — is formula phi a theorem?No (only semi-decidable)Validity of first-order logic is undecidable in general; a prover may run forever on an unprovable formula

Why This Matters for AI Systems

An inference engine reasoning over a knowledge base needs to evaluate predicates and compute functions as part of proving goals. If a predicate is not computable, no algorithm can guarantee an answer in finite time — this is a fundamental limitation, not an engineering shortcoming.

ConsequenceExplanation
Restricted logic subsets are used in practiceSystems like Prolog restrict to Horn clauses, a decidable-in-practice subset of first-order logic, to guarantee usable inference
Some queries may not terminateA general theorem prover asked "is this formula true?" for an unprovable formula may search forever
Function evaluation must be side-effect-free and well-definedSo the same input always yields the same, predictable output — essential for consistent reasoning

Connecting Back

Computable functions and predicates are what let the facts written in the previous two lessons (Marcus the Pompeian, Tweety the canary) actually be used by a program — not merely stored as inert text, but queried, combined, and reasoned over automatically.