Hacker News Reader

Comment by dragontamer | Hacker News Reader

IIRC, some language model proved that one-layer of loops can be proven to halt vs not-halt.

As soon as you add a 2nd layer of loops however, you reach Turing-completeness and suddenly the halting problem becomes unsolvable.

-------

So you don't need to deny jmp/loops. You just need to deny _nested_ loops. And... find that old paper I read like 15 years ago to figure out the details to discriminate halt/not-halt in the single-layer loop language.

View on HN

This is most assuredly false:

    while (state !== STOP):
       read = TAPE[index]
       [state, write, dir] = TABLE[read, state]
       TAPE[index] = write
       index = index + dir

It takes much more. You need to e.g. limit APIs you can call to ones that are also guaranteed to halt, and guarantee an exit condition that is guaranteed to occur, which means either seriously limiting input or adding additional implicit conditions.

E.g. this Ruby program is undecidable:

    gets

This one using a hypothetical gets guaranteed to eventually halt is still undecidable:

    while getsWithTimeout != "halt"
    end

You could ask ChatGPT to find the paper for you! It told me the name of an old videogame I was trying to remember for years.

Reply on news.ycombinator.com