Talk:X-complete
Jump to navigation
Jump to search
This sounds like a circuit complexity class. Corbin (talk) 01:34, 3 December 2025 (UTC)
Interesting idea
what if some language was X-complete but NOT Turing-complete? --JITJITJITJITJITJIT 08:46, 3 December 2025 (UTC)
what if some language was NOT X-complete but still Turing-complete? --JITJITJITJITJITJIT 08:49, 3 December 2025 (UTC)
- That would be interesting, but very hard if not impossible, as Turing-completeness requires a way to do some arithmetic FluixMakesEsolangs (talk) 14:36, 3 December 2025 (UTC)
- Surprisingly, no. Check out Aardvark, But Is It Art?, and Wang tiles for counter-examples. Turing-completeness merely requires that computable functions are represented; it's sufficient for the structure of an individual program to imply arithmetic without having any arithmetic operators. Food for thought: Turing machines don't have built-in arithmetic either! Corbin (talk) 14:59, 3 December 2025 (UTC)
- Wow, I never knew that before thats actually kinda cool, I guess you really do learn something new every day. - FluixMakesEsolangs (talk) 15:02, 3 December 2025 (UTC)
- Surprisingly, no. Check out Aardvark, But Is It Art?, and Wang tiles for counter-examples. Turing-completeness merely requires that computable functions are represented; it's sufficient for the structure of an individual program to imply arithmetic without having any arithmetic operators. Food for thought: Turing machines don't have built-in arithmetic either! Corbin (talk) 14:59, 3 December 2025 (UTC)
- That would be interesting, but very hard if not impossible, as Turing-completeness requires a way to do some arithmetic FluixMakesEsolangs (talk) 14:36, 3 December 2025 (UTC)
Clarification
what exactly does "functionally complete logic or arithmetic between an arbitrary number of values" mean? —aadenboy (talk|contribs) 14:47, 3 December 2025 (UTC)
- Functionally complete logic is logic that can recreate all other logic, like how NAND and NOR are functionally complete, and an arbitrary amount is "any" amount, so like between 2 values is like "2+2" but 4 values is like "4*(9/3)-7", it's a rule so X-Complete sytems are actually usable for computation, I might've explained horribly or completely wrong, but that should be hopefully be the answer you're looking for. FluixMakesEsolangs (talk) 15:44, 3 December 2025 (UTC)