1. Forum
  2. Fidonet
  3. COMP.LANG.C

  • Re: Alan Turing's Halting Problem is incorrectly formed --- My first p

    From olcott@3:633/280.2 to All on Mon Aug 25 07:56:34 2025
    Subject: Re: Alan Turing's Halting Problem is incorrectly formed --- My first
    post on the halting problem

    On 6/6/2004 9:11 AM, Peter Olcott wrote:
    One very simple transformation of the problem into a solvable problem
    is to convert the Boolean function DoesItHalt() into a tertiary response: True, False, Neither.

    if (DoesItHalt() == True)
    while(True) // loop forever
    ;
    else if (DoesItHalt() == False)
    return False;

    else if (DoesItHalt() == NeitherTrueNorFalse)
    return NeitherTrueNorFalse;

    So the original Halting Problem was incorrectly formed specifically
    because it was framed as a Boolean function, thus failing to account
    for possible inputs that result in a reply other than True or False.





    --
    Copyright 2024 Olcott

    "Talent hits a target no one else can hit;
    Genius hits a target no one else can see."
    Arthur Schopenhauer

    --- MBSE BBS v1.1.2 (Linux-x86_64)
    * Origin: ---:- FTN<->UseNet Gate -:--- (3:633/280.2@fidonet)
  • From olcott@3:633/280.2 to All on Mon Aug 25 08:19:44 2025
    Subject: Re: Alan Turing's Halting Problem is incorrectly formed --- My first
    post on the halting problem WHOLE THREAD

    On 8/24/2025 4:56 PM, olcott wrote:
    On 6/6/2004 9:11 AM, Peter Olcott wrote:
    One very simple transformation of the problem into a solvable problem
    is to convert the Boolean function DoesItHalt() into a tertiary response:
    True, False, Neither.

    if (DoesItHalt() == True)
    ˙˙ while(True)˙˙ // loop forever
    ˙˙˙˙ ;
    else if (DoesItHalt() == False)
    ˙˙ return False;

    else if˙ (DoesItHalt() == NeitherTrueNorFalse)
    ˙˙ return NeitherTrueNorFalse;

    So the original Halting Problem was incorrectly formed specifically
    because it was framed as a Boolean function, thus failing to account
    for possible inputs that result in a reply other than True or False.






    https://www.usenetarchives.com/view.php?id=sci.logic&mid=PGJDRndjLjEzOTgwJEd4NC4yNTM3QGJndG5zYzA0LW5ld3Mub3BzLndvcmxkbmV0LmF0dC5uZXQ%2B

    --
    Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
    hits a target no one else can see." Arthur Schopenhauer

    --- MBSE BBS v1.1.2 (Linux-x86_64)
    * Origin: A noiseless patient Spider (3:633/280.2@fidonet)