Great video to excite people about theory of computation. The idea of models such as these warps my mind (in a good way), and makes me really think about how we program.
very interesting concept! essentially, your model "accepts an input" if there exists some arbitrary number of rows for which you can tile the wall in a valid way. this essentially interprets the columns as "space", and the rows as "time", and you can think of the model as a set of non-deterministic rewriting rules operating on a finite input tape until every cell reaches some "final" state (the bottom wall color). that makes the equivalence with a linear bounded non-deterministic turing machine pretty clear. what i think is interesting is that you can reverse this interpretation: you can think of rows as space, and columns as time. a wall with a single row corresponds very directly to a non-deterministic finite state machine, where the available tiles are the available transitions. the top color is the input symbol, the left color the current state, and the right color the next state. to extend this to multiple rows, have the bottom color of the tile be the output of the FSM, which is fed into the FSM below it. what this shows is that a chain of arbitrarily-many copies of an FSM is equivalent in computational power to a linear bounded automaton!
I don't think this video really explains much. You mention time complexity, but you don't say how that concept even applies to this model. If it measures the order of how many rows are required for a tiling, that's not measuring time. The process that actually finds those tilings has a time complexity, but it will not be able to count the number of ones in a string of length N in O(1) time as you suggest it could. It does not seem apt to compare this to programming at all.
Time complexity is something that you need to define for the computational model that you're working with and you can define it however you'd like. For this one in particular, I was interested in finding the tilesets and exploring how many rows they need to tile (since I think those are the interesting problems here), not a fast algorithm that does the tiling. And for those, since columns are fixed, you really can't do much besides counting the rows.
@@YTomSwhy do you need to define that for a model that does not involve time? its an extremely unintuitive notion, so even if its true you have to explain why its useful. i can absolutely understand the need for *some* primary measure of complexity, but how can this be compared to time? as it stands, you dont mention any sort of nuance, so anyone who takes your explanation at face value without understanding its implications will be wildly misled as to what this model can do. because again, no programming model will be able to count N objects in O(1) *time*.
This content is so advanced. Thank you for the video.
Great video to excite people about theory of computation. The idea of models such as these warps my mind (in a good way), and makes me really think about how we program.
very interesting concept!
essentially, your model "accepts an input" if there exists some arbitrary number of rows for which you can tile the wall in a valid way. this essentially interprets the columns as "space", and the rows as "time", and you can think of the model as a set of non-deterministic rewriting rules operating on a finite input tape until every cell reaches some "final" state (the bottom wall color). that makes the equivalence with a linear bounded non-deterministic turing machine pretty clear.
what i think is interesting is that you can reverse this interpretation: you can think of rows as space, and columns as time. a wall with a single row corresponds very directly to a non-deterministic finite state machine, where the available tiles are the available transitions. the top color is the input symbol, the left color the current state, and the right color the next state. to extend this to multiple rows, have the bottom color of the tile be the output of the FSM, which is fed into the FSM below it. what this shows is that a chain of arbitrarily-many copies of an FSM is equivalent in computational power to a linear bounded automaton!
T++ for the win!
I once had a homework problem about these :)
Fantastic content quality
Hey that's pretty good
Thanks, what tools used for the video?
All of the tools I used are linked in the description 🙂.
how to check parentheses in log(N)?
There is a link in the description to the article where the solution is explained: slama.dev/youtube/bathroom-tile-programming/
Amazing video, how to you make these animations ?
All software I used is mentioned in the description. Animations specifically were made with Manim.
Looks like toy chemistry.
I don't think this video really explains much. You mention time complexity, but you don't say how that concept even applies to this model. If it measures the order of how many rows are required for a tiling, that's not measuring time. The process that actually finds those tilings has a time complexity, but it will not be able to count the number of ones in a string of length N in O(1) time as you suggest it could. It does not seem apt to compare this to programming at all.
Time complexity is something that you need to define for the computational model that you're working with and you can define it however you'd like.
For this one in particular, I was interested in finding the tilesets and exploring how many rows they need to tile (since I think those are the interesting problems here), not a fast algorithm that does the tiling. And for those, since columns are fixed, you really can't do much besides counting the rows.
@@YTomSwhy do you need to define that for a model that does not involve time? its an extremely unintuitive notion, so even if its true you have to explain why its useful. i can absolutely understand the need for *some* primary measure of complexity, but how can this be compared to time? as it stands, you dont mention any sort of nuance, so anyone who takes your explanation at face value without understanding its implications will be wildly misled as to what this model can do. because again, no programming model will be able to count N objects in O(1) *time*.
first