3 ms·

Previous discussion: May 19, 2021 - https://news.ycombinator.com/item?id=27202801 https://news.ycombinator.com/item?id=27202801 (40 comments)

by folmar 3y ago

musicale 3y ago
"It is well-known that the x86 instruction set is baroque, overcomplicated, and redundantly redundant. We show just how much fluff it has by demonstrating that it remains Turing-complete when reduced to just one instruction." – MOV is Turing-complete, Stephen Dolan, 2013 discussion (2013) https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=6309631 [While I concur that x86 MOV is impressively powerful, it is also well-known that simple NAND gates can be combined to compute arbitrary logic functions. There are also many simple single instruction/operation CPU designs.]
- loxias 3y ago
  > [While I concur that x86 MOV is impressively powerful, it is also well-known that simple NAND gates can be combined to compute arbitrary logic functions. There are also many simple single instruction/operation CPU designs.] Strong agree. My fav example in the same category as "all circuits can be made with just nand" and "all you need is x86 MOV" is the iota formal language. If the lambda calculus is too luxurious, and SKI combinators are too bloated, try using iota for all your language theory needs! No unnecessary concepts, or the two redundant operators of SKI! just one "simple" primitive: i := λf.((fλa.λb.λc.((ac)(bc)))λd.λe.d) There, now you're turning complete. ;-)
  - tromp 3y ago
    iota just packages S and K together in a tuple. The simpler A = λx.λy.λz.x z(y (λ_.z)) suffices for Turing completeness. (tough) Challenge: derive S and K from A.
    - loxias 3y ago
      1. <3 Thanks! This fact is now filed with the same neuron that fires for "wang tiles", "rule 110" and that new "hat" tile. 2. Does that simpler "A" combinator have a name, or something I can google for or find in mathworld and read more about? My interest, and estimate of ability, level is right at "not gonna do the work myself, but I'd enjoy following the proof/paper". ;-) 3. see: #1. I love learning about abstract and completely useless and impractical mathematical constructions, as a contrast to my day job making computers be useful. :)
      - tromp 3y ago
        No, it doesn't have a standard name. The "A" is just a placeholder name. It was only discovered last year as a shortest possible one-point basis, and hasn't been publicized much.
        loxias 3y ago
        I just realized you're likely the same person who made a more recent and compact binary encoding, for algorithmic information theory/Chaitin's constant purposes!! I'm humbled, and have been a fan of the field for a long time. :D I'm no mathematician, just most of my family and friends ;-) ~23 years ago I (and some other math major and grad student friends at college -- "my people") would get into great enjoyable late night chats about AIT. Mostly with me arguing "there's something cool/legit math here!" and them being healthily skeptical. I've always had a penchant for the computational and experimental discovery, of course my brother is the polar opposite. I'd be honored to collaborate on, well, anything, should you ever need the skills (pro bono, of course) of an professional, experienced, HPC/C++ scientific programmer who knows a bit of math as well. ;-)
        tromp 3y ago
        Yep, that's me. I got interested in AIT when one of the luminaries of the field taught a course on it in University and I went on to do a PhD under him. Would have been happy to join in your late night chats:-) As you can see on my home page, I love to do research related programming myself, but also welcome other people contributing with their expertise.

Previous discussion: May 19, 2021 - https://news.ycombinator.com/item?id=27202801 https://news.ycombinator.com/item?id=27202801 (40 comments)

by folmar 3y ago

Previous discussion: May 19, 2021 - https://news.ycombinator.com/item?id=27202801 https://news.ycombinator.com/item?id=27202801 (40 comments)

musicale 3y ago

"It is well-known that the x86 instruction set is baroque, overcomplicated, and redundantly redundant. We show just how much fluff it has by demonstrating that it remains Turing-complete when reduced to just one instruction." – MOV is Turing-complete, Stephen Dolan, 2013 discussion (2013) https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=6309631 [While I concur that x86 MOV is impressively powerful, it is also well-known that simple NAND gates can be combined to compute arbitrary logic functions. There are also many simple single instruction/operation CPU designs.]

loxias 3y ago
> [While I concur that x86 MOV is impressively powerful, it is also well-known that simple NAND gates can be combined to compute arbitrary logic functions. There are also many simple single instruction/operation CPU designs.] Strong agree. My fav example in the same category as "all circuits can be made with just nand" and "all you need is x86 MOV" is the iota formal language. If the lambda calculus is too luxurious, and SKI combinators are too bloated, try using iota for all your language theory needs! No unnecessary concepts, or the two redundant operators of SKI! just one "simple" primitive: i := λf.((fλa.λb.λc.((ac)(bc)))λd.λe.d) There, now you're turning complete. ;-)
- tromp 3y ago
  iota just packages S and K together in a tuple. The simpler A = λx.λy.λz.x z(y (λ_.z)) suffices for Turing completeness. (tough) Challenge: derive S and K from A.
  - loxias 3y ago
    1. <3 Thanks! This fact is now filed with the same neuron that fires for "wang tiles", "rule 110" and that new "hat" tile. 2. Does that simpler "A" combinator have a name, or something I can google for or find in mathworld and read more about? My interest, and estimate of ability, level is right at "not gonna do the work myself, but I'd enjoy following the proof/paper". ;-) 3. see: #1. I love learning about abstract and completely useless and impractical mathematical constructions, as a contrast to my day job making computers be useful. :)
    - tromp 3y ago
      No, it doesn't have a standard name. The "A" is just a placeholder name. It was only discovered last year as a shortest possible one-point basis, and hasn't been publicized much.
      - loxias 3y ago
        I just realized you're likely the same person who made a more recent and compact binary encoding, for algorithmic information theory/Chaitin's constant purposes!! I'm humbled, and have been a fan of the field for a long time. :D I'm no mathematician, just most of my family and friends ;-) ~23 years ago I (and some other math major and grad student friends at college -- "my people") would get into great enjoyable late night chats about AIT. Mostly with me arguing "there's something cool/legit math here!" and them being healthily skeptical. I've always had a penchant for the computational and experimental discovery, of course my brother is the polar opposite. I'd be honored to collaborate on, well, anything, should you ever need the skills (pro bono, of course) of an professional, experienced, HPC/C++ scientific programmer who knows a bit of math as well. ;-)
        tromp 3y ago
        Yep, that's me. I got interested in AIT when one of the luminaries of the field taught a course on it in University and I went on to do a PhD under him. Would have been happy to join in your late night chats:-) As you can see on my home page, I love to do research related programming myself, but also welcome other people contributing with their expertise.