Recognition and Decision featuring YesOnString

Cullen Doyle, Issei Hasegawa, Preston Smith

October 27, 2025

Decision

• What is Decision?
  • Accepts and halts when the string is in the language (positive instance).
  • Rejects and halts when the string is not in the language (negative instance).

Recognition

• What is “Recognition”?
  • A language or decision problem always accepts and halts on all positive instances.
  • Either rejects and halts or loops forever when the string is not in the language (negative instance).
  • Example: A C++ compiler(g++) checks whether a program is syntactically correct. If the syntax is valid → it halts and accepts. If invalid → it may reject with an error or keep processing indefinitely.

Similarities & Differences

• What are Similarities & Differences?
  • Similarities
    • Both guarantee correct acceptance for “Yes” instances.
    • Both are defined using Turing machines.
  • Differences
    • Decision “Always” halts in finite time, while Recognition “May not” halt for some inputs.
    • Decision corresponds to both ‘Yes’ and ‘No’ cases, while Recognition corresponds only to the ‘Yes’ case.

Recognition Visualized

Positive Instance

Positive Instance

Negative Instance

Negative-Instance-Orange

<<

Negative-Instance-Jammed

• Only guaranteed to receive a fruit if it’s an apple
• There’s a chance the machine jams if an apple isn’t passing through
• A decidable version of this situation is if the result could only be an apple or orange

Recognition is Easier than Decision

• Why Recognition is Easier than Decision?
  • Recognition try to find only positive instance; it does not care about Negative instance and infinite loop.
  • Decision try to find all possible case; it must correctly distinguish all cases (both yes- and no-instances)

What is RecYesOnString?

• What is RecYesOnString?
  • Takes two inputs: a Python program P as a string and an input string I.
  • Runs the program P with I as the input: P(I)
  • Outcomes:
    • If P halts and prints “yes”, then RecYesOnString prints “yes”.
    • If P halts and does not print “yes”, then RecYesOnString prints “no”.
    • If P does not halt, then RecYesOnString does not halt.

RecYesOnString Program

# This can be found in the "What Can Be Computed?" book.

# returns: If P(I) is 'yes', returns 'yes'. If P(I) terminates but
# does not return 'yes', then 'no' is returned. If P(I) enters an
# infinite loop, this program also enters an infinite loop.

import utils; from utils import rf
from universal import universal  
def recYesOnString(inString):
    (progString, newInString) = utils.DESS(inString) 
    val = universal(progString, newInString)  
    if val == 'yes':
        return 'yes'
    else:
        return 'no'  

Recognizes, but Does Not Decide

• How does this Recognize and not Decide?
  • RecYesOnString only considers the positive instance of the YesOnString program.
  • If anything but the positive instance is returned, then RecYesOnString returns “no”.
  • This is different than deciding, since deciding a program requires the program to halt: choosing either “yes” or “no”.