Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: I made a programmable computer from NAND gates

github.com

Post reply on HN
Print view View original

61–70 of 80 posts

Re: Show HN: I made a programmable computer from NAND gates

#61

Post by cellularmitosis »

dhosek wrote: post #26
moefh wrote: post #20

Earlier quoted context omitted.

There's this one that goes one step beyond that, it's built out of 40,000 discrete transistors: https://www.youtube.com/watch?v=z71h9XZbAWY EDIT: there's more information here: https://www.megaprocessor.com/

I kind of want something midway between the FPGA version and the all-transistor version, something that just uses 7400 series chips (or, presumably there’s a 26-pin equivalent with 6 gates instead of three). Heck, I think even something that goes ahead and uses the full panoply of basic logic chips available could be kind of cool to see.

Slu4 has a great series of videos about exactly what you are looking for, with his Minimal 64 computer https://youtu.be/FJsnKu20ch8

61 TTL chips mentioned in this 8 minute overview https://youtu.be/3zGTsi4AYLw

Re: Show HN: I made a programmable computer from NAND gates

#62

Post by rational_indian »

schoen wrote: post #60
rational_indian wrote: post #57

Earlier quoted context omitted.

>Could you have a few different-sized square waves continue to cycle through the circuit? No.

Could you help improve my intuition about that, or give me a reference where I could learn more?

First look up Barkhausen criteria, then read the following. For ring oscillators gain will be greater than unity for only those waves whose period matches the gate delay. Only one such wave exists since the gate delay is a fixed number.

Re: Show HN: I made a programmable computer from NAND gates

#63

Post by cubefox »

tomstuart wrote: post #34
cubefox wrote: post #25

Cool project. It reminds me of a theoretical issue. As the project page says, this system is clearly Turing equivalent. Since it runs software, it even implements a _universal_ Turing machine. But the design uses only (synchronic) sequential logic [1] and Wikipedia seems to suggest that automata theory considers sequential logic only equivalent to finite state machines. Not Turing machines. Isn't that clearly a major…

Real-world computers are equivalent to linear bounded automata, not true Turing machines, because they have finite memory. This technicality is mostly ignored because a computer with a large finite memory is a decent enough approximation to a Turing machine for practical purposes. But, for example, the halting problem is decidable for linear bounded automata — because there are only finitely many states, every comput…

It seems you didn't really read my comment though? I was arguing the relevant difference between Turing machines and FSMs was the memory system, not its infinite tape. It's interesting that the Wikipedia article on LBAs doesn't tell us whether they are considered equivalent to FSMs. It seems that by standard automata theory, they must be. Which is intuitively not the correct, since they are much more similar to Turing machines.

Re: Show HN: I made a programmable computer from NAND gates

#64

Post by syockit »

Animats wrote: post #28
dhosek wrote: post #27

Earlier quoted context omitted.

The supercomputers (all?) used wirewrap rather than PCBs. I heard a story once about someone coming in for a demo of a supercomputer and Cray realized there was a bug in the hardware during the demo and while the potential customers were at lunch, he rewired the machine to fix the bug.

Right. Seymour Cray said that the two big problems in supercomputing were "the thickness of the mat" (of wires on the backplane) and getting rid of the heat. This is a Cray-I backplane.[1] [1] https://www.flickr.com/photos/geekmuseum/2926520634/

I wonder if any of his machines ever caught fire, causing an localized out-of-season aurora borealis. On the other hand, Cray machines are never mentioned in the "Halt and Catch Fire" machine code instruction humor.

Re: Show HN: I made a programmable computer from NAND gates

#65

Post by userbinator »

rational_indian wrote: post #62
schoen wrote: post #60

Earlier quoted context omitted.

Could you help improve my intuition about that, or give me a reference where I could learn more?

First look up Barkhausen criteria, then read the following. For ring oscillators gain will be greater than unity for only those waves whose period matches the gate delay. Only one such wave exists since the gate delay is a fixed number.

It is possible for a ring oscillator to generate harmonics: https://ieeexplore.ieee.org/iel5/16/31849/01482193.pdf

Re: Show HN: I made a programmable computer from NAND gates

#66

Post by tomstuart »

cubefox wrote: post #63
tomstuart wrote: post #34

Earlier quoted context omitted.

Real-world computers are equivalent to linear bounded automata, not true Turing machines, because they have finite memory. This technicality is mostly ignored because a computer with a large finite memory is a decent enough approximation to a Turing machine for practical purposes. But, for example, the halting problem is decidable for linear bounded automata — because there are only finitely many states, every comput…

It seems you didn't really read my comment though? I was arguing the relevant difference between Turing machines and FSMs was the memory system, not its infinite tape. It's interesting that the Wikipedia article on LBAs doesn't tell us whether they are considered equivalent to FSMs. It seems that by standard automata theory, they must be. Which is intuitively not the correct, since they are much more similar to Turin…

I did read your comment but I don’t really understand what you mean by “the memory system”. A linear bounded automaton is by definition a finite state machine for a given input (i.e. fixed tape size) because the number of possible configurations is finite. A Turing machine’s infinite tape is what stops it being a finite state machine.

Re: Show HN: I made a programmable computer from NAND gates

#67

Post by c0wb0yc0d3r »

marai2 wrote: post #31
ryeguy_24 wrote: post #24

This is amazing work. I wanted to build something similar (virtual) while I was taking the Nand2Tetris course. I'm so impressed that you actually did it. You must have a really good understanding of how computers work now.

And I was just thinking about the same thing this morning, using SVG to model the basic components. And lo and behold somebody has done a magnitude more amazing job then what I was imagining!

You still can! :)

I have just embarked on this journey myself, recently. It is motivating to see others' work. Especially when they're not quite the same as what I'm doing.

Re: Show HN: I made a programmable computer from NAND gates

#68

Post by rational_indian »

userbinator wrote: post #65
rational_indian wrote: post #62

Earlier quoted context omitted.

First look up Barkhausen criteria, then read the following. For ring oscillators gain will be greater than unity for only those waves whose period matches the gate delay. Only one such wave exists since the gate delay is a fixed number.

It is possible for a ring oscillator to generate harmonics: https://ieeexplore.ieee.org/iel5/16/31849/01482193.pdf

Interesting, would have loved to read the paper. Unfortunately I don't have an IEEE subscription right now.

Re: Show HN: I made a programmable computer from NAND gates

#69

Post by IncreasePosts »

rational_indian wrote: post #68
userbinator wrote: post #65

Earlier quoted context omitted.

It is possible for a ring oscillator to generate harmonics: https://ieeexplore.ieee.org/iel5/16/31849/01482193.pdf

Interesting, would have loved to read the paper. Unfortunately I don't have an IEEE subscription right now.

https://sci-hub.ru/10.1109/T-ED.1982.20696

Re: Show HN: I made a programmable computer from NAND gates

#70

Post by krallja »

DEADMINCE wrote: post #58
tomstuart wrote: post #34

Earlier quoted context omitted.

Real-world computers are equivalent to linear bounded automata, not true Turing machines, because they have finite memory. This technicality is mostly ignored because a computer with a large finite memory is a decent enough approximation to a Turing machine for practical purposes. But, for example, the halting problem is decidable for linear bounded automata — because there are only finitely many states, every comput…

> because there are only finitely many states, every computation must either halt or eventually revisit an earlier state and get stuck in a loop Yet we know this doesn't happen in practice.

You just didn’t wait long enough.
Post reply on HN