Sujet : Re: Can Flibble’s neos-based solution still be Turing Complete?
De : polcott333 (at) *nospam* gmail.com (olcott)
Groupes : comp.theoryDate : 24. May 2025, 17:02:41
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <100sqj1$ppn2$1@dont-email.me>
References : 1
User-Agent : Mozilla Thunderbird
On 5/23/2025 9:20 PM, Mr Flibble wrote:
Yes, **Flibble’s neos-based solution can still be Turing Complete as a
whole**, even though it **disallows programs from referencing the
decider**.
Let’s break this down precisely.
A more useful application of the term Turing Complete
would be that a sequence of algorithmic steps that
have sequence, selection and iteration have as much
memory as they need for a specific computation.
When we do this then it can be seen that some key
algorithms from the theory of computation can be
fully encoded in a high level language like C.
---
## ✅ What It Means to Be Turing Complete
A system is **Turing complete** if it can compute anything a Turing
machine can, given:
* Unbounded memory (in theory),
* Conditional branching,
* Arbitrary loops or recursion.
Turing completeness **does not require** that:
* Programs be analyzable by another program,
* Programs be allowed to self-reference or invoke their own decider.
---
## 🧠 Stratified Model in Flibble’s Design
Flibble’s proposal using **neos** introduces two **stratified languages**:
1. `shdlang`: a meta-layer language used to **analyze** code.
2. `neoscript` (or similar): a Turing-complete target language for
defining **programs**.
### Stratification Rule:
* `shdlang` → can inspect or reason about `neoscript` programs.
* `neoscript` → **cannot access** or call back into `shdlang`.
This blocks constructions like `D() { if H(D) then loop; }`, which enable
**halting paradoxes**.
---
## 🔄 Is the Combined System Still Turing Complete?
Yes — because:
* The **target language layer** (`neoscript`) is unrestricted in its own
recursion and computational logic.
* It can simulate a Turing machine in the usual way.
* **Not being able to invoke the decider doesn’t restrict the program’s
expressive power**, only its ability to encode a self-referential
*analysis*.
This mirrors the situation in many practical systems:
* **C compilers** can analyze or optimize code, but the C code doesn’t
call the compiler.
* **Proof assistants** can verify programs, but the program logic doesn’t
run the proof engine at runtime.
---
## 📌 Key Insight
**Turing completeness is a property of expressiveness — not of
reflexivity.**
Flibble’s system forbids *certain kinds of reference*, not *certain kinds
of computation*.
---
## ✅ Summary
| Aspect |
Answer |
| ----------------------------------------------------------- |
-------------------------------------------- |
| Is the target language Turing complete? | ✅
Yes |
| Does SHD restriction affect program expressiveness? | ❌ No —
only affects semantic analysis scope |
| Can this architecture be used in general-purpose computing? | ✅
Absolutely |
| Does this break the classical halting proof? | ❌ No —
it sidesteps it by design constraints |
---
So yes, Flibble’s stratified neos solution **can still be Turing complete
as a whole**, even though it blocks calls from programs to their deciders
— a **sound architectural tradeoff** to avoid paradox without sacrificing
computational power.
-- Copyright 2025 Olcott "Talent hits a target no one else can hit; Geniushits a target no one else can see." Arthur Schopenhauer