Introduction To Symbolic Dynamics
ฝัง
- เผยแพร่เมื่อ 5 ก.ค. 2024
- This video was made for 3 Blue 1 Brown's Summer of Math Exposition 2 competition.
This is a brief summary of some of the more central elements in the field of Symbolic Dynamics.
Some applications of symbolic dynamics for anyone interested (all 4 are worth watching):
Wave function collapse • Superpositions, Sudoku... and • Why I'm Using Wave Fun...
Cellular automata • Coding Adventure: Ant ...
Tiling spaces • The Infinite Pattern T...
0:00 - Introduction
0:31 - Dynamical Systems
1:10 - Baker’s Map
2:28 - Binary Fractions
3:08 - Baker’s Map on Binary Fractions
4:28 - Symbolic Dynamics Introduction
6:08 - Simple Example
6:34 - Subshifts
7:58 - Golden Mean Shift
9:09 - Even Shift
9:40 - Shift Invariant Rules
10:18 - Adjacency Rules
11:22 - Local Rules
12:03 - Shifts of Finite Type
13:05 - Simple Machines
14:51 - Sliding Block Codes
15:55 - Conjugacy
17:28 - Closing
Errors:
At 2:29 it should be b1,b2,b3,... not all b1. Also, natural numbers start at 1, not 0 as shown in much of the video.
#some2
![ความรักไม่ได้น่ากลัวขนาดนั้น (TRUST ME) - LYKN [ OFFICIAL MV ]](http://i.ytimg.com/vi/9np-lAtCRpQ/mqdefault.jpg)
Just wanted to say how well produced this video was. The topic was cool, and, as a basic introduction, it was executed incredibly well. Great work!
Thanks!
Amazing! Couldn't have asked for a more clear and informative explanation.
Would love a series on this topic!!
One of my favourite some2 videos for sure
Same!
Whenever you find something new in maths never forget to check whether it can be used to solve the 3k+1 problem!!!
Wonderful video, something I've never looked into or heard of directly but your video made me glad to learn! It reminds me of matrix representations in group theory as well. I hope you continue making content like this and I look forward to your next video!
A very fast but thorough introduction. Great job!
Haven't watched this yet but been doing a bunch of hobby work on Rule 30 so I'm really excited to watch!!!!
Absolutely amazing video! Subscribed.
I was somewhat waiting for the appearance of finite state automata and was quite happy when the Turing machine and cellular automata were mentioned. Seems to be tightly related to this topic. Thank you for the introduction.
any mention of cellular automata gives me a math boner
Nice , informative video. Reminded me Mathologer 's new video on number walls
Nice video! I’m also glad to see Atkinson Hyperlegible being used out in the wild!
I didn't know about this font before this comment, but it's a very interesting font. Thanks for turning me on to it
One thing that the video seems to omit is what is this good for. It's nice to learn the basic operations, but for someone who has never seen this before it might be useful to show an application of these techniques.
Yes, that would have been nice, but the video builds up to about the point where we could start talking about examples and then I ran out of time. We have a brief cellular automata demo, but those are much more interesting in 2d, which we also didn’t have time to get into. Symbolic dynamics is similar to general group theory in that it is a framework you can shift a problem into to get a different perspective or to make things easier to work with. There are also some applications where symbolic dynamics is generally the starting framework, for example:
Wave function collapse th-cam.com/video/2SuvO4Gi7uY/w-d-xo.html , th-cam.com/video/20KHNA9jTsE/w-d-xo.html
Cellular automata th-cam.com/video/X-iSQQgOd1A/w-d-xo.html
Tiling spaces th-cam.com/video/48sCx-wBs34/w-d-xo.html
Markov chains
I hope that helps.
@@syllabusgames2681 I watched the video hoping for some insight on graph paths or strings to solve some weird problems I currently solve other ways
Really well put together, I wonder how this correlates with group theory when talking about sub shifts
Awesome intro to a niche topic!
Really cool video , thank you!
LOVE THIS VIDEO!
Excellent video
Wow! One thing I'm left wondering: the "even groups of zeros" rule _is_ recognisable by a finite state machine (regular expression), does this hold any significance in this field?
The fact that a finite state machine/regular expression can recognize the language of the even shift is a reflection of the fact that the even shift is *sofic*. Sofic shifts are a class of subshifts that includes SFTs, and also some other shifts that may not be SFTs but still enjoy some nice "finitary" description.
In particular, a subshift is sofic if and only if there is a regular expression which recognizes all allowed words of the subshift, and no forbidden words. Every SFT is sofic because if you have a finite list of words to avoid, you can write a (possibly very long and cumbersome, but) finite regex to accept all words NOT containing any of the forbidden words as subwords.
From a more dynamical perspective: if you take an SFT and push it through a sliding block code, the image is a sofic shift. All sofic shifts are realized in this way.
@@mrpengywinz123 Sounds like EVEN is a good example of a sofic shift that's not finite type.
@@cmilkau that is correct! It is one of the most basic examples of a strictly sofic shift
Really interesting field of mathematics!
super cool!!!
4:05 actually if π is used as the base, then you could specify it exactly as it equals 1 (base-π).
bro thanks so much. dis video is tiless 3 years ltr n still great
i don't know what some2 is but there's been some very high quality videos with that tag
Any plans to expand on symbolic dynamics or any other math topic? This topic is fairly niche and i wonder what other kind of math interests you!
Very useful bro I like it
very interesting
I enjoyed you presentation, and would like to seem more. The only notes that I'd add are
1) some parts moved very quickly with many things happening simultaneously, such that I had to pause the video to see what all the moving pieces were.
2) your pronunciation of comBINaTORics rather than the common and traditional COMbinaTORics was a little jarring; I assume it is a regionalism.
3) I would have made the window clearer, at least when first introduced, as it was hard to see where the windows were (I do understand, however, that you had to balance that against overlaps when putting in a lot of windows to explain local vs global).
Overall quite entertaining and enjoyable.
Thank you for the suggestions! Yours is the most useful feedback I have received, and I will try to avoid similar problems in the future.
1) There were defiantly more elegant ways to show some parts of the video. Like my explanation of decimal binary: I should have known not to have 5 numbers updating at once.
2) Yes. Rob (who wrote the script) mentioned I was pronouncing it wrong, but after listening to some clips of it being said, I couldn’t hear a difference and just left it. And of course, this was mere hours before it was due.
3) That is a good point. I should have made the windows larger on screen instead of introducing them on a 20+ symbol example shift. At 360p, the window’s sides are probably 2 pixels across.
@@syllabusgames2681 Honest answers. I'm looking forward to more of your work in the future.
Excellent video! I just have one question---is there a reason for your choice to use singly-infinite sequences in this video? i.e. A^N
In my SymDy class, we used bi-infinite sequences from A^Z, which I think more naturally captures our human picture of a system that evolves over time (e.g. the ability to "rewind a video" and look at its past). It just seems awkward to delete the first character when you use the shift function
There is a reason, but not a good one. Most of the script was focused on A^N, so when we were looking for things to cut to get it done on time, we noticed bi-infinite series were only mentioned 2 or 3 times and didn't really connect to anything. I would like to have kept it, but as I was editing this together hours before it was due, I don't think we could have afforded to. But you are right; it belongs in this video. It just didn't fit.
As for deleting the first symbol when shifting, while awkward, it is a real thing you have to deal with using singly-infinite series.
@@syllabusgames2681 Makes sense, it's a shame that these things have to get cut, but I understand it's necessary in the process of editing. Nevertheless, great video! :D
the main difference between the shift map on A^N and A^Z is that on A^Z the shift map is invertible, while on A^N the shift map is not invertible in general (due to deleting the first symbol). So if you are studying a dynamical system out in the wild which is not in general invertible, you might expect to be able to encode it using a symbolic system over N rather than Z. Another approach is to try to "extend" the function to a wider domain where it becomes invertible, then use the bi-infinite sequences to encode the dynamics of the extended map.
14:00 " Shift of Finite Type... SFT" Bravo.
I wish I could comment on the content. Thank you!
15:54 that part reminds me of busy beavers
This is exactly like a stream of audio data
Thank u so much, interested in starting so soft during quarintine and just need a place to get started, thx for the support
Nice, but make a hashtag in video name
Thanks. I forgot that was a thing.
Interesting
oh nice are we going to do an even odd shift where alphabet is {a,b,c} {odd, even, one} and require a validator which checks if current node and next node are not (a,c)
super cool i was confused bc i was like left to right scan i can store info in one but (flip odd even) and raise error if odd (1 causes read state)
lovely video with in depth explanation but 1 question. How does one do the importings
Thanks, but I'm not sure what you're asking. This was made in Unity using a bunch of script I wrote myself if that answers your question.
The symbol with the subscript 8 is the 9th place.
I feel like this would have applications in logic and formal languages.
Sadly i comprehend comprehend very little of this, though it seems to be exactly the subject I've been trying to identify, for years really, in relation to at certain pattern I became somewhat obsessed with, when i first learned about bitboard and their rotations i 2-d, which naturally i had to expand into n-d.
When i had finally identified the entire sequence, or at least that is and was my belief, just for the run of it, i tried to print it out in binary. Imagine my surprise when a certain triangular fractal presented itself.
Hei man! I thought your comment to be very interesting but I didn't understand it very well.
Could you please explain to me in detail how to get the pattern, or how to write a program that makes it, or something like that?
@@adamsmainchannel3789 It is not really all that difficult, once figured out, but perhaps difficult to explain. Regardless I shall make and attempt.
This subject first came to my attention, when I discovered the "Delta Swap" function, which is quite useful, especially when working with Bit Boards.
U64 deltaSwap( U64 b, U64 mask, int delta ) {
U64 x = (b ^ (b > delta) ^ b;
}
/* NB: this function can be written in two ways, impacting the needed mask, depending on the direction of the bitshift. The result is essentially the same, just mirrored
Chessprogramming DOT org is a great resource for learning more about this and much more.*/
I noticed a pattern in the Masks, and became very focused on completing it, so to speak, though I didn't really understand it.
At some point I thought I had, but still, I didn't really see the connection. For some reason I decided to print the masks I had generate out in binary, and lo and behold, out popped the Sierpinski Triangle in one's and zero's. Quite amazing, but still, I didn't have the complete picture, and really it is only just recently that I have arrived at a point have a reasonable understanding.
For bit widths of 2^n, there are 3^n patterns and accompanying delta values. though for use with the delta Swap, only (n^3-1)/2(+1) are actually useful, the +1 in parenthesis sort of a NULL pattern, which can be applied without any effect. The remain patterns performed the same task, just in reverse, which in this case is the same, or rather it doesn't make a different if you swap the first and the last bit, or the last and the first.
The patterns can be created reasonably easily.
let's take the example of bit width 8, or or n = 3. This tells us that there are 27 patterns in total.
firstly, we need to generate the base patterns, and there are several ways of doing so.
In this case the patterns are:
mask / delta
0x0f, 4
0x33, 2
0x55, 1
and my favorite way of generating these is as follow:
mask = -1; //-1 = all ones
for( delta = 1= 1 )
{
mask 55)
----
mask, delta
0x02, 5
deltaSwap( 0b00000111, 0b00000010, 5 )
would then return 0b01000101
Other masks and delta values may be used, and the list generated is not exhaustive in that way, but I do believe that this list of patterns is complete relating to arriving at all the rotational symmetries of any Bit Board int any applicable dimension for the given bit width. for N = 3, that would be only 1 and 3 dimensions, while for 64 for bits, it would be 1, 2, 3 and 6.
I suppose this is the best I can do just now, but I think it is all correct, and though it may sound complicated, it really isn't and I will do my best to answer any questions.
Best regards.
To be honest this video felt a little frustrating. There were a lot of definitions that felt really tantalizing, like it will provide you with a change in perspective that makes some seemingly impossible problem tractable, or give some unexpectedly neat connections. And I was excited for what it leads up to, because it looks really cool, but it just lead to more definitions.
It's like an introductory lecture at uni, except that there are no follow up lectures.
Sorry about that. This material is new to me too, which made it a little hard to plan things out. If you want to see how this stuff is applied to real problems, I have some pretty interesting videos linked in the description. Sadly, getting to that material in my video would have taken at least 10 more minutes of explaining 2d bi-infinite series, entropy, and likely a few other pieces of groundwork to built up to the examples rather than skipping to them, and I just didn’t have time.
In the future, I will focus on topics I fully understand, so the videos should be significantly better structured and more complete.
Dude, you speak so fast! 😊
7:47
8:08
Ok I'll stop now
The conjugacy problem has "incomputable" smell all over it.
You used the wrong symbol for proper subset. You used \subseteq which means "subset or equal" (this symbol is often used interchangeably with \subset). \subsetneq is the symbol for proper subset.
And WHAM! Well you're drunk now!
I can't listen to this and the non-descript piano clanging in the back ground..
Aw. I thought I finally made it quite enough. I guess it would be best to just have no music while I'm talking.
Nice video, but if you introduce something new, you don't have to tell like 4 different terms for it. Maybe there are different names for many concepts, but telling them all is totally irrelevant in a video like this.
e.g.: 7:31 "We refer to these systems as subshifts, shift spaces or shifts interchangeably"
Maybe it is done in the literature, but this throwing around with names just distracts from the actual content. Just stick to one term for the video and call it a day.
You're right; I probably should have done a find and replace on the script so every reference to a subshift called it a subshift instead of just "shift." Then I wouldn't have needed to say every synonym at once. I wanted to mention when something had multiple terms so viewers doing further reading on the subject wouldn't get tripped up by other material using different terms, but it should have been more of a footnote later on than the "internalize these 3 terms right now" I currently have.
soft would be the sun... Or maybe the earth? Fuck nvm. Point is I can't thank you enoughfor these tutorials. I've been playing guitar for
1 automaTON
2 automaTA
Please stop embarrassing yourself (and confusing others) with such easily avoidable mistakes in content that takes so much effort to make.
the thempo of the voice is rather high, 🏔️ as if there is to much to be said, and thus cramped up in to short a time ⏳, this makes it more difficult to understand, and in my situation the translation to my motherthong (Dutch) is lagging 🐌 However it was an eye opener 👀 on a topic, that I just didn't know it exists, many 🙏 for this!