Re: Can Flibble’s neos-based solution still be Turing Complete?

On 5/24/25 12:02 PM, olcott wrote:

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.
 

The one issue is that the C language establishes that there *IS* a limit to the size of a pointer, and thus how much memory the program can occupy.
Thus, a given implementation MUST have an upper limit on memory.
An algorithm can be expressed in C, and as long as it does no operation that establishes what that limit is, could be run on an implementation that is sufficiently large to handle that computation.
This is actually a common approximation, that a finite processor, can be considered doing an operation defined on an umbounded processor as long as that processor didn't need more memory than is available.
If the operation needs more memory than available, the approximation is just violated, and a larger machine is needed.
If the operation results in truely unbounded behavior, then no finite approximation is possilbe.
The trick here is determining THAT the results are truely unbounded behavior, and not just a larger bound than has currectly been found, as is the question with some of the unsolved problems.
What has been proven is that there exists at least one program that will use truely unbounded memory, but which can not be proven to do so with only finite memory.

 

---
>
## ✅ 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.