51–60 of 79 posts
https://codegolf.stackexchange.com/questions/11880/build-a-w...
Here's something I wonder: Imagine you're stuck on an island or in a forest, and you're stuck with what you find in nature only, or perhaps you get very primitive technology (e.g. basic metal working only): What's the simplest way you could build some (mechanical) logic gates to do some form of useful computation? I've seen some from lego or 3D printed ones, but they all look very complicated, e.g. requiring rubber b…
Earlier quoted context omitted.
Suckerpinch is one of the best youtube channels out there, I love his work. I came here to link this once I saw the title, but you've already done it! He reminds me of what Forth people get so excited about, fitting so much into such small places.
If you like his stuff you should check out the sigbovik proceedings each year. Most of his videos are about his papers there and he has even more papers he doesn't make videos about! I don't think anybody else is making papers as interesting as his (about half are just jokes with no real content) but there are other gems of a similar "work hard on a fundamentally silly problem" vein.
Is pure gold. I don't wanna spoil it, it just keeps getting better and better as the video progresses. I laughed so hard.
If by some freak chance I ever become wealthy, I want to sponsor this sort of research.
the claim is that this is theoretically possible in stock tetris with only one modification: an infinite board (with a floor). the infinite board solves piece randomization, because you can have a "junkyard" where you dump pieces until you get the one you want. it also solves the time pressure, because blocks spawned at row inifinity will never reach the canvas until you hard-drop them. finally, it prevents rows from…
You want to know how the Tetromino does memory allocation and garbage collection? I don't think the infinite board is that big of a deal. Turing Machines and Lambda Calculus have no limits on their memory space and we implement analogues of them in our limited memory space.
> On an infinite playfield, tetrominoes spawn at “row infinity” and column zero. When a newly spawned piece falls, it never gets closer to the floor due to the nature of infinity. This means, in finite—though potentially vast—time, the agent can shift the piece into any finite column. And once in position, the agent can hard drop the piece.
gate construction relies on "nudging" a block at a specific row as it is falling. but if blocks start at row infinity, the only way to get them down should be to hard-drop them -- which precludes nudging.
they've defined a new "semi-hard-drop" operation, and introduced it as a "generalization" of legal moves, but it isn't.
Earlier quoted context omitted.
If you like his stuff you should check out the sigbovik proceedings each year. Most of his videos are about his papers there and he has even more papers he doesn't make videos about! I don't think anybody else is making papers as interesting as his (about half are just jokes with no real content) but there are other gems of a similar "work hard on a fundamentally silly problem" vein.
https://www.youtube.com/watch?v=HLRdruqQfRk (Uppestcase and Lowestcase Letters [advances in derp learning]) Is pure gold. I don't wanna spoil it, it just keeps getting better and better as the video progresses. I laughed so hard. If by some freak chance I ever become wealthy, I want to sponsor this sort of research.
The C Compiler that only emits the printable bytes is my favorite one by a mile. The executables can only jump forward and only by an offset between two modestly large numbers. This makes laying out the code in the executable a really interesting problem and relies on weird old behavior where the instruction pointer can wrap on overflow. Wild!
Earlier quoted context omitted.
If you like his stuff you should check out the sigbovik proceedings each year. Most of his videos are about his papers there and he has even more papers he doesn't make videos about! I don't think anybody else is making papers as interesting as his (about half are just jokes with no real content) but there are other gems of a similar "work hard on a fundamentally silly problem" vein.
Is there an easy way to look all of them up?
Here's something I wonder: Imagine you're stuck on an island or in a forest, and you're stuck with what you find in nature only, or perhaps you get very primitive technology (e.g. basic metal working only): What's the simplest way you could build some (mechanical) logic gates to do some form of useful computation? I've seen some from lego or 3D printed ones, but they all look very complicated, e.g. requiring rubber b…
relevant xkcd: https://xkcd.com/505/
ref: https://writings.stephenwolfram.com/2020/04/finally-we-may-h...
It seems like I quite often see posts here about how $thing$ can perform universal computation, or simulate a UTM, or whatever. And obviously the HN readership selects for these articles. But is there any significance to be found in all these things having this attribute? Does it tell us anything about the universality of computation as a property of the universe? I seem to recall that sed and C++ template installati…
I guess the main takeaway is that you do not need much in order for something to be Turing-complete. On the other hand this should hardly be surprising, all you need is something to store a state and the ability to alter the state in a few different ways depending on the current state, and of course the ability to do this over and over again. The more surprising thing should maybe be that this is all you need and tha…
Interestingly, DNA computation can behave like a non-deterministic Turing machine. [0] However, as you mention, there is a clear trade-off between resources and time complexity. In this instance, the amount of DNA needed to solve an NP-Complete problem with a large input, e.g. n = 256, would require more atoms than there are in the observable universe given that the amount of DNA needed grows at a rate of 2^n.
[0] https://www.sciencedirect.com/science/article/pii/S030439750...
I just got a terrible idea: combine this with another project, that built Tetris in Conway's Game of Life. That would enable executing an arbitrary program in Tetris, simulated in Game of Life. https://codegolf.stackexchange.com/questions/11880/build-a-w...
Earlier quoted context omitted.
I guess the main takeaway is that you do not need much in order for something to be Turing-complete. On the other hand this should hardly be surprising, all you need is something to store a state and the ability to alter the state in a few different ways depending on the current state, and of course the ability to do this over and over again. The more surprising thing should maybe be that this is all you need and tha…
Hey Danbruc, Interestingly, DNA computation can behave like a non-deterministic Turing machine. [0] However, as you mention, there is a clear trade-off between resources and time complexity. In this instance, the amount of DNA needed to solve an NP-Complete problem with a large input, e.g. n = 256, would require more atoms than there are in the observable universe given that the amount of DNA needed grows at a rate o…
So I think saying DNA computation can behave like a non-deterministic Turing machine is only true in the same sense that a deterministic Turing machine can behave like a non-deterministic Turing machine, i.e. not very true. The difference is the trad-off - exponentially slower vs exponentially more processing units - and there might be some use for this if you have, for some n, enough room for exponentially many DNA molecules but not enough time to wait for exponentially many clock cycles.
The primary advantage of a DNA computer might be that you can make use of all three dimensions while processors are mostly limited to two dimensions. I did not read the paper you linked to, but the DNA computations I have seen where all very slow processes, so at least in those cases I have seen, the DNA computation has to make good for many orders of magnitude of processing speed in terms of parallelism before there is even the possibility of an advantage.