91–100 of 103 posts
Earlier quoted context omitted.
> demonstrated that printf() is Turing complete and wrote a first person shooter in ... Not gonna lie, I thought that sentence would end with the FPS being done in printf.
This guy wrote tic-tac-toe in a single call to printf for IOCCC 2020 competition: https://github.com/carlini/printf-tac-toe
I fear not the man who plays chess with 84,688 regular expressions, but I fear the man who plays chess with one regular expression.
help, I'm being nerd-sniped
right away I see backreferences as a potential problem
it would be a VERY long regex, but you're basically encoding a chess engine, so...
I fear not the man who plays chess with 84,688 regular expressions, but I fear the man who plays chess with one regular expression.
If there was a general heuristic to make sequentially-applied regexes linear (combine any 2 into 1), it could be applied to this help, I'm being nerd-sniped right away I see backreferences as a potential problem it would be a VERY long regex, but you're basically encoding a chess engine, so...
Just breathe
Close your eyes
Picture an algebraic representation of the higher order function that represents your real life utility and minimizes the use of resources including your cognitive energy.
Focus on optimizing that function.
Ohmmmmm
Earlier quoted context omitted.
I'll happily admit that there is (to me) no reason to believe that humans can do things that a Turing machine could not, or that we are magically exempt from stuff like the halting theorem or have special insights in NP-complete problems. I am only arguing that we are unarguably more powerful than FSMs, and with some pen and paper (or perhaps an endless string of tape...) we are not as limited by our working memory s…
These sorts of power discussions require a certain amount of grace, unless you're really just super, super excited to read several paragraphs of intensely mathematical caveats, not just from the first poster, but from every poster in such a thread. There is a reasonable sense in which we can say with a straight face that humans are more powerful than finite state machines, even though in principle a human's entire li…
You don't need to have every state in an FSM be explicitly constructed up-front.
The pdf you mention is great, btw.
And just in time when the novelty of playing chess in Postscript (https://seriot.ch/projects/pschess.html) has worn off :)
Earlier quoted context omitted.
> a first person shooter in 13kB of Javascript I was somewhat disappointed to realize they used WebGL for rendering the graphics.
There was an earlier version of the underlying 3d engine that used only Canvas. WebGL use is justified like this: > Once I actually got that working doing all of the math by hand in JavaScript I decided that using WebGL would probably be worth it, and actually probably wasn't cheating all that much. WebGL exposes access to the GPU-enabled rendering engine through JavaScript. While it does abstract away some of the re…
You could argue that rasterization itself is being taken care by the implementation, though.
Earlier quoted context omitted.
Regex isn't (necessarily) turing complete :) > Because our program just consists of a sequence of regular expressions, you can't loop at all! That, technically, means we can't actually perform Turing Complete But we can do any bounded computation by just unrolling any loops we may have. Although some (most?) implementations may be. Though by the above quote, the author didn't make use of that.
That's the point, I think: for a large number of real-world algorithms, you don't actually need a Turing Machine. There was a very well-written explanation of this on the front page[1] some time ago, concluded with: > Any algorithm that can be implemented by a Turing Machine such that its runtime is bounded by some primitive recursive function of input can also be implemented by a primitive recursive function! Also,…
Earlier quoted context omitted.
That's the point, I think: for a large number of real-world algorithms, you don't actually need a Turing Machine. There was a very well-written explanation of this on the front page[1] some time ago, concluded with: > Any algorithm that can be implemented by a Turing Machine such that its runtime is bounded by some primitive recursive function of input can also be implemented by a primitive recursive function! Also,…
I appreciate the resources and recommendations. I've been interesting in Rocq (formerly Coq) recently, and I've seen dependent types mentioned, so I've been curious to learn more.