Conversation

Notices

1. Embed this notice
   Haelwenn /элвэн/ :triskell: (lanodan@queer.hacktivis.me)'s status on Saturday, 04-Nov-2023 07:34:30 JST Haelwenn /элвэн/ :triskell:

   • Sexy Moon
   • LEdoian
   @ledoian @Moon Regexes aren't really well-defined and ended up way beyond what a regular language is, which by very definition doesn't allows to get a turing machine.
   • Embed this notice
     Haelwenn /элвэн/ :triskell: (lanodan@queer.hacktivis.me)'s status on Saturday, 04-Nov-2023 09:51:21 JST Haelwenn /элвэн/ :triskell:

     in reply to

     • Sexy Moon
     • LEdoian
     @ledoian @Moon Point: *All* computers are memory constrained, even if you'd figure a way to botnet the internet and do swap over it.
   • Embed this notice
     LEdoian (ledoian@pleroma.ledoian.cz)'s status on Saturday, 04-Nov-2023 09:51:23 JST LEdoian

     in reply to

     • Sexy Moon

     @lanodan @Moon For finite-state machines, regular languages are sufficient. And it can be argued that a memory-constrained computer is a finite-state machine (a state is the immediate contents of registers, memories, drives, &c; inputs are clocks and I/Os. The number of states is finite (though absurdly large) and the state change is well-defined for any input).

     So it theoretically should be possible to create an actually-regular expression describing a “computation” of a computer (but not an unbounded Turing machine).

     (TIL: there seems to be a convention that “regular expressions” are expressions describing regular languages, and “regexes” are the patterns used in programming languages, regular or not.)

   • Embed this notice
     Haelwenn /элвэн/ :triskell: (lanodan@queer.hacktivis.me)'s status on Saturday, 04-Nov-2023 09:53:27 JST Haelwenn /элвэн/ :triskell:

     in reply to

     • Sexy Moon
     • LEdoian
     @ledoian @Moon And yes it limits computation, because there's moments where data simply doesn't fits in your computer, be it registers, cache, RAM, storage, …
   • Embed this notice
     Haelwenn /элвэн/ :triskell: (lanodan@queer.hacktivis.me)'s status on Saturday, 04-Nov-2023 10:01:13 JST Haelwenn /элвэн/ :triskell:

     in reply to

     • Sexy Moon
     • LEdoian
     @ledoian @Moon Except not everything memory-bounded are FSM, computers would be quite different and without say an halting problem if that were the case.
   • Embed this notice
     LEdoian (ledoian@pleroma.ledoian.cz)'s status on Saturday, 04-Nov-2023 10:01:14 JST LEdoian

     in reply to

     • Sexy Moon

     @lanodan @Moon I think we just got stuck on some minor misunderstanding. Moon said that all Turing machines are equivalent at computation. You remarked that for memory-constrained programs that is not the case, and the Turing machine does not exist IRL. And to that I argued that there are only finite computers IRL, therefore equivalent to finite-state machines, finite automata, regular expressions…, which are also all equivalent at computation :-)