logoalt Hacker News

vintermanntoday at 5:58 AM2 repliesview on HN

Yes, this article is kicking in open doors, the original article was quite clear about the scope.

The present article could rather have spent time arguing why this isn't like NAND gate functional completeness.

I would have thought the differences lie in the other direction: not that trees of EML and 1 can describe too little, but that they can describe too much already. It's decidable whether two NAND circuits implement the same function, I'm pretty sure it's not decidable if two EML trees describe the same function.


Replies

reikonomushatoday at 6:37 AM

You are correct, it is undecidable by Richardson's theorem [1].

[1] https://en.wikipedia.org/wiki/Richardson%27s_theorem

show 1 reply
zephentoday at 1:13 PM

> It's decidable whether two NAND circuits implement the same function

Well, sure. At least, until you have a loop that starts clocking for you, and now you've got the halting problem.