An Impossible Program

# Please see here an excellent animation for the halting problem and proof
# https://youtu.be/92WHN-pAFCs?t=240

# Short version, assume H, describe H', show the contradictoin arising from executing H'(H').
# Sure, we've all seen that before, but what if we actually execute H'(H')?

# Below you will find an H/HALT and an X/OPPOSITE that do both possibilities.
# H/HALT is described as a Turing Machine which can determine if a program and an input will halt or run forever.
# Infinite loops and infinite stacks must therefore be detectable by H.
# Please allow some code outside HALT() to fulfill this detection function since I am not a godlike machine.
# Please allow the function HALT to take the place of H the Turing Machine
# X/OPPOSITE is described as a Turing Machine which will do the opposite of what H returns.
# Please allow the function OPPOSITE to take the place of X the Turing Machine
# Some print statements were added to allow one to track the return values of various invocations of HALT and OPPOSITE/H&X.
# As you will see in its output, HALT is correct in determining OPPOSITE's behavior.
# OPPOSITE can either enter an infinite loop or return a value.  HALT says it will do both and it does both.
# The proof assumes OPPOSITE(OPPOSITE) is called and thus we call it here.
# OPPOSITE(OPPOSITE) will thus execute HALT(OPPOSITE,OPPOSITE).
# If HALT executes OPPOSITE(OPPOSITE) we enter an infinite loop.  HALT can detect infinite loops.

# I hereby show if HALT exists, then HALT exists without contradicting its own existence.
# At least according to the usual proof that's so popular.
# Hopefully this will encourage someone to show a better one.
# I dislike this form of the proof.  H is capable of doing just about anything and I feel at a minimum
# it's been installed with logical paradox crumple zones.

# Some more formality, let Opp0 be the first copy of OPPOSITE which is called, Opp1 is the second, etc.
# Let H0 be the first copy of HALT called, let H1 be the second, etc.
# When H0 detects an infinite loop, oh, I never specified what it does!
# Certainly it must, at some point, terminate the loop, otherwise it won't be able to return an answer.
# So if H0 terminates the loop immediately and returns 'NOSTOP', Opp0 will return HALTS and of course, halt.
# H0 would be wrong!  I guess all this is for naught and we should pack up and go home.
# While we're packing up, let's let H0 continue running a bit more.  I'm sure that won't change anything.
# If H0 allows it to keep going, H1 will detect the infinite loop in Opp1.
# Well, H0 can safely terminate the loop at this point, if it didn't, H1 will then wait to terminate the loop, etc.
# How to terminate?  Well, H1 did all that work, might as well let it finish and return a value.
# H1 will see that Opp2 loops forever, which it would if we let it, so well, H1 is correct.
# Opp1 will see that H1 returns 'NOSTOP' and thus Opp1 will return HALTS, and thus Opp1 halts.
# H0 will see that Opp1 halts, and H0 is correct, as we have just seen Opp1 halt.
# So every instance of H that produced an answer has produced a correct answer.

import sys
# setting to even and odd will determine outcome of top level OPPOSITE (the one called directly)
sys.setrecursionlimit(6)

class HaltDetectedInfinity(Exception):
    def somefn():
        return 'a'

# This is for tracking things in the program and implementing HALT's infinity detection
GLOBAL_INFINITIY_COUNTER = int(0)

def OPPOSITE(INPUT):
    global GLOBAL_INFINITIY_COUNTER
    current = GLOBAL_INFINITIY_COUNTER
    GLOBAL_INFINITIY_COUNTER += 1
    #print("current",current)
    if HALT(INPUT, INPUT) == 'HALTS':
        localCounter = 0
        while True :
            print("HALT SAID I'D HALT BUT OPPOSITE WILL NEVER HALT HAHAHA")
            localCounter += 1
            # HALT may be able to detect infinite loops, but I have to resort to stopping them
            if localCounter > 5 and current > 0:
                raise HaltDetectedInfinity('A ' + str(GLOBAL_INFINITIY_COUNTER))
            # top level return because I need my computer back
            # This is not a part of HALT's deliberations
            if localCounter > 5 and current == 0:
                print("returning top level OPPOSITE, I'd like to run other scripts now");
                return 0
            # we'll ignore this exception for the top level OPPOSITE because halt might not be running,
            # when halt is running this is part of HALT that detects infinite loops
            if current != 0:
                raise HaltDetectedInfinity('B')
    else :
        #print("HALT SAID I'D RUN FOREVER BUT OPPOSITE WILL ALWAYS HALT HAHAHA!", current)
        print("HALT SAID I'D RUN FOREVER BUT OPPOSITE WILL ALWAYS HALT HAHAHA!")
        return 'HALTS'

# returns 'HALTS' if INPUT1(INPUT2) halts
# returns 'NOSTOP' if INPUT1(INPUT2) doesn't halt
def HALT(INPUT1, INPUT2) :
    global GLOBAL_INFINITIY_COUNTER
    current = GLOBAL_INFINITIY_COUNTER
    if INPUT1 == HALT :
        return 'HALTS' # that answer should be obvious
    if INPUT1 != HALT and INPUT1 != OPPOSITE :
        print("left as exercise for reader")
        exit(0)
    try:
        result = INPUT1(INPUT2)
    except HaltDetectedInfinity as ex:
        msg, = ex.args
        #print("machine doesn't stop", GLOBAL_INFINITIY_COUNTER, msg)
        #print("NOSTOP REACHED", GLOBAL_INFINITIY_COUNTER, msg)
        print("'NOSTOP' reached, HALT detected infinite loop", msg)
        return 'NOSTOP'
    except RecursionError as ex2:
        msg, = ex2.args
        # in case you want to count stack overflow as a machine halting, comment out return 'NOSTOP'
        #print("machine halt detected by HALT", current)
        #print("machine halt detected by HALT")

        # If a Turing Machine has access to infinite tape, we're detecting an infinite loop
        print("'NOSTOP' reached, HALT detected infinite loop", msg)
        return 'NOSTOP'
    print("'HALTS' reached, program terminated")
    return 'HALTS'

try:
    #print("GLOBAL_INFINITIY_COUNTER",GLOBAL_INFINITIY_COUNTER)
    OPPOSITE(OPPOSITE)
except HaltDetectedInfinity as ex:
    print("we'll ignore this exception since halt isn't running")
GLOBAL_INFINITIY_COUNTER = int(0)
print("---------------------------")
#print("one result of two:",HALT(OPPOSITE,OPPOSITE))

# thanks for reading