Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Although [Gödel 1931] failed to proved inferential

undecidability of Russell's Principia Mathematica, there is a

fairly simple undecidable proposition namely, the proposition

   *Undecidable*≡Halt<ExpressionFromString<Natural>>[RunOne.[]]
where RunOne.[]≡Eval.[SelectOne.[0]] such that

   SelectOne.[i:Natural]≡ExpressionFromString<Natural>.[i] *finishesFirst* SelectOne.[i+1]
Eval.[anExpression] evaluates anExpression and where the expression

    (expression1 *finishesFirst* expression2)
returns the value of whichever of the expressions expression1

and expression2 evaluation finishes first.

The procedure SelectOne selects one of the expressions

created from strings.

For details see: https://papers.ssrn.com/abstract=3603021



There is a small typo in the above:

Undecidable ≡ Halt<ExpressionFromString<Natural>>[⦅RunOne.[]⦆] is

inferentially undecidable in the theory Actors, that is,

Undecidable and ⊬¬Undecidable where

RunOne.[]≡Eval.[SelectOne.[0]] and ⦅RunOne.[]⦆ is the

expression for the procedure application RunOne.[]




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: