p
e
r
s
o
n
a
l |
Anagraphs and Generalized Kerning
(22 Dec 2017 at 18:17) |
Well, merry checklistmas etc., I finally got something done this month; it's this:
Anagraphs movie; rated G for general audiences
The movie above is another fun project, I hope entertainingly explained, with some twists. It concerns the dismemberment of letters to generalize anagrams, which I call anagraphs. It was presaged in post 1146 which may give you some idea how long it takes me to finally finish such projects. This one lended itself to some interesting computational problems, which I wisely realized would better exist in a completely separate video; it's this:
51 minute lecture about Turing Machines, Linear Logic
This latter movie is far less polished and rated C for College, because it's basically a lecture about decidability, specifically two uses of the technique of reduction to prove an undecidability result, and then a decidability result. If you like that kind of stuff, you will probably enjoy it, but if not, you were warned!
Also crossed off the checklist, I 100%ed Super Mario Odyssey and finished some books I was reading, as well as keeping up my streak of running every single day (today was #159). This makes my slate clean to start on new projects, a state that I just love being in, and will likely postpone through the holiday! Happy new year to you! |  |
|
So with 159 days, how much have you run so far?
(Turing machine lecture runs like an MITCourseWare video by the way) |
| Hey Tom, loved both new videos. I really enjoyed your lecture and would love to see more Tom Academy videos in the future, especially ones about logic as I find it fascinating. Keep up the great work as always and congrats on the 159 day running streak, that's great! |
Thanks folks! I'm glad that the lecture video seems to have found an audience. :)
I don't actually take my watch on every run, especially when I'm doing an indoor treadmill where it's hard to measure the actual "mileage." So I don't really know. But it's at least 708 miles, since that's the total that I did record during the period. Not bad; that's at least 30 miles a week. |
That's quite a lot.
Also, why do the comments record IP addresses? |
Nitpicking time! I'll complain about a technical detail that you could just leave an exercise for the reader in an ordinary article, but since this is an introductory kind of video that pretends to be very precise, I get to do this.
Your definition of the halting problem asks if the tape ever gets into a specific state. The tape is potentially infinite, padded with zeros. Your reduction of the halting problem to the kerning problem makes sure the tape is expanded with zeros when necessary, but it never shrinks the tape. How do you then reduce checking for a specific state of the tape to checking for a specific destination word in the kerning problem, when the latter word could be padded with an unknown an unbounded number of zeros?
|
Shantanu: Well, it just allows anyone to comment without making an account, so the IP addresses are to provide some form of accountability. For example I use them to ban spammers. :) This was very common practice when I wrote this blog software (e.g. on IRC you could always see the IP address where each person was connecting from); I hadn't really thought about the fact that this is not common any more. Normally it shows the reverse DNS, but I guess my reverse DNS server was not functioning.
jonas: Precision nitpicks are certainly welcome! I think this is a gap in the "proof" (and a good example of the kind of thing you have to account for when you REALLY formalize something). It seems like you could easily handle this by adding rules like "{0 <=> {" and "0} <=> }", which would then allow the deletion of any extraneous zeroes, which yields a single normalized representation of any Turing machine state with no leading or trailing zeroes (treating the cursor's location as also nonzero). I avoided using rules like this because they add ambiguity to what rules apply at any given moment, which makes other reasoning harder (you need to think about equivalence classes of states, I guess). |
Tom I absolutely LOVE your videos and your work, you are extremely talented! How do you remain so creative and motivated? Do your ideas just come to you or do you have some kind of brainstorming work flow I could steal?
(Side note: Would you consider releasing the font editor you made? I would love to play around with it if you did.)
|
You still have a few hours to post.
|
Thanks Nate! There is no one secret, but I will say:
- Write down all your ideas, even the bad ones.
- Always use your best idea; don't hoard them.
- Every project has awful slogs in it and your body and brain tell you to just give up. Not giving up in those moments is what I think it feels like to "be creative," so you just have to be willing to suffer that stuff.
It seems you can use the editor straight from the source repository:
http://svn.code.sf.net/p/tom7misc/svn/trunk/anagraph/editor-ceors.html
Begin by hitting backtick to switch modes, but you probably need to view the source code (editor.js) to make any sense of the UI. Unfortunately you won't be able to save without downloading the helper app and compiling it (and good luck; it's Standard ML), so it won't be that usable except just to mess around. But obviously feel free... |
| for getting rid of trace and spare turing tape, make it so that the letter representing halted state (let's call it H) can combine with character to either side to become itself, and delete everything else that way, and lone H would be the destination word. If the starting word couldn't reach “blah H blah” in the first place, it wouldn't have an h to perform the "draw anything" trick with (catch 22, basically). All rules are reversible, so a word that can't reach the destination (H) can't be reached from destination either |
I am not convinced by your proof that "generalized kerning" (which i understand to mean arbititrary finite kerning + arbititrary finite ligatures) is undecideable.
I followed your proof but i would not describe it as "generalized kerning" but as "generalized kerning with substring acceptance".
I suspect your substring extension is necessary to proof undecidedability because "generalized kerning" (without substring acceptance) is decideable. You observation that generalized kerning can implement a turing machines is correct. I suspect that "generalized kerning" (without substring acceptance) is bounded in a similar manner to how tape bounded turing machine are bounded (and decideable).
I think all ligatures and kerning examples you presented were "local enough" and seem to require less then what a context-sensitive rewriting system would offer. Which are decideable as off (2020) https://verify.rwth-aachen.de/giesl/papers/GieslMiddeldorp-distribute.pdf . I think the ability to hide an arbitrary amount of steps allows you to escape bounds of the world of linear bounded turing machine.
You would need a description of the rules of generalized kerning to get a more detailed answer. |
|
|
|
|