‘undecidable’能否在ASP（回答集编程）中表示？附两种尝试方案分析

Great question—let's unpack this step by step. You're aiming to model a scenario where if a(X) is true, we can't determine whether a(X) qualifies as b(X)—in other words, you want to capture a state of undecidability around b(X) for instances where a(X) holds. Let's break down your attempted solutions and what ASP can (and can't) do here.

Your Tried Approaches #

Attempt 1: b(X) | -b(X) :- a(X). #

This disjunctive rule creates a choice: whenever a(X) exists, both b(X) and -b(X) are allowed as valid options in answer sets. While this lets both possibilities coexist, it doesn't actually model "undecidability" in the strict sense. ASP solvers will happily generate both answer sets if possible—this just means there are multiple valid models, not that the problem is undecidable. The solver can still compute all possible outcomes, so there's no true uncomputability here.

Attempt 2: :- a(X), b(X). and :- a(X), -b(X). #

These are hard constraints that reject any answer set where a(X) is paired with either b(X) or -b(X). Since in standard ASP, the closed-world assumption means -b(X) is inferred if b(X) isn't asserted—so whenever a(X) exists, these constraints trigger a contradiction, making the program unsatisfiable. This is the opposite of undecidability—it's a clear conflict the solver detects immediately.

So, Can ASP Represent "Undecidability"? #

Short answer: Not in the computational theory sense you're thinking. ASP is a decidable formalism—for finite programs, solvers can always compute answer sets (or prove none exist). Undecidability refers to problems where no algorithm can correctly answer yes/no for all inputs, which isn't something you can encode within ASP's semantics.

If your goal is to model incomplete information (we don't have enough data to conclude b(X) or -b(X) when a(X) holds), here are the closest workarounds:

• Stick with the disjunctive rule from Attempt 1: it lets multiple answer sets exist, each representing a possible state of knowledge (either b(X) is true or false).
• Avoid adding any rules about b(X) when a(X) holds: under standard closed-world semantics, -b(X) will be inferred, but if you use ASP extensions with open-world semantics, b(X) can remain unassigned (reflecting that we don't know).

But neither of these captures true undecidability—they just model uncertainty or missing information within ASP's decidable framework.

内容的提问来源于stack exchange，提问作者Pay C.