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

Liste des GroupesRevenir à theory 
Sujet : Re: Can Flibble’s neos-based solution still be Turing Complete?
De : polcott333 (at) *nospam* gmail.com (olcott)
Groupes : comp.theory
Date : 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; Genius
hits a target no one else can see." Arthur Schopenhauer

Date Sujet#  Auteur
24 May 25 * Re: Can Flibble’s neos-based solution still be Turing Complete?8olcott
24 May 25 +- Re: Can Flibble’s neos-based solution still be Turing Complete?1Richard Damon
25 May 25 `* Re: Can Flibble’s neos-based solution still be Turing Complete?6Mikko
25 May 25  `* Re: Can Flibble’s neos-based solution still be Turing Complete?5olcott
26 May 25   `* Re: Can Flibble’s neos-based solution still be Turing Complete?4Mikko
26 May 25    `* Re: Can Flibble’s neos-based solution still be Turing Complete?3olcott
26 May 25     +- Re: Can Flibble’s neos-based solution still be Turing Complete?1Richard Damon
27 May 25     `- Re: Can Flibble’s neos-based solution still be Turing Complete?1Mikko

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal