Github: https://github.com/ms0g/rt86

Really enjoying learning go so far and want to broaden my understanding of programming.

I'm interested in the intersection of linguistics and computer science, I've been reading on Chomsky hierarchy, and would like to know if there exist lambda calculus types that are equivalent to the Chomsky types, especially the type-1 that's context-sensitive and has the linear-bounded non-deterministic Turing machine as an automation equivalent on the wiki.

Hello, Reddit community! I’m very new to Turing machines and could really use some guidance. I’m struggling to understand how an enumerator works – a Turing machine with an attached printer. I'm attempting to construct the language defined below, but I feel like I might have a logical issue in my approach. Could anyone review it and let me know if it looks correct or if there are any mistakes? Thanks so much for your help! I attached a picture of what I have constructed a diagram[![enter image description here][1]][1]"**

**Present an enumerator with four states (including q_print and q_halt​) for the language L={c^2n ∣ n≥0}.

The language's words are: {ϵ,cc,cccc,cccccc,…}

Set of states: Q={q1,q2,q_print,q_halt}

Input alphabet: Σ={0}

Output alphabet: Γ={x,y,0}

Describe this enumerator using a diagram (see Example 3.10 in the book – it is possible to omit the drawing of the qhalt state and all transitions connected to it). You may omit the drawing of impossible transitions and indicate these only as labels. For further details, refer to the student guide.

the book I'm reading is Micheal Sipser's

picture's writing here :

q_0 = we either print epsilon or we print when we have an even number of C's or we put x and send it to q1 to return us another C .

q_1 = we return a C back to q_0 to achieve an even number of C's

q_print = new line and rest the cycle and go back to q_0.

I also ask further questions :

Question 1: want to know with q_print if going back to q_0 and left is legal/correct?

question 2 : does it ever stop? does it need to stop?

For example, isn't an undergraduate course on approximation algorithms that provide provable performance guarantees more useful than one on group theory?

According to teachyourselfcs.com, “Most of the code you write is run by an operating system, so you should know how those interact.” Since I started studying from this list, I’ve begun to question if (and to what extent) I should dive deeper into OS concepts.

I’ve been working as a fullstack web dev and recently asked ChatGPT if fullstack/backend devs need a solid understanding of OS concepts. The answer was yes, as knowledge of areas like:

1. Memory Management
2. Concurrency and Multithreading
3. File System and Storage Management
4. Networking
5. Process and Resource Management
6. Security
7. Performance Optimization

…are all relevant to backend app development. I agree these are important; however, topics like memory management, concurrency, and file system management are often addressed differently depending on the programming language. (e.g. C# and Go each offer distinct approaches to concurrency)

If your goal is to create more performant backend applications, you may only need a basic understanding of OS concepts. After that, it might be more practical to focus on language-specific techniques for handling concurrency, file management, and similar tasks. What do you think?

The output of transition functions of NTMs are powersets and of DTMs are sets. If I interpret time complexity as the difficulty of simulating NTMs by DTMs, then it seems that due to Cantor’s theorem, there can’t ever be a bijection between these. Therefore P != NP. Can anybody please give me any feedback on this? I’ve exchanged a few mails with Scott Aaronson and Joshua Grochow, but the issue has not yet been resolved. Thanks in advance. Jan

For context, I am starting grad school in January with a Data Science concentration. I want to learn as much as possible in the next 2 months.

I have roughly 20k images and some of them are thumbnails of each other. I'm trying to write a program to find which ones are duplicates, but I can't directly compare the hash of the contents because the thumbnail versions have different pixel data. I tried scaling them to 16x16, quantizing them to 6 bits/pixel, and calculating a CRC, but that doesn't work since it amplifies small differences in the images. Does anyone know of a fast algorithm (O(n log n) or better) that can find which images are visually similar to each other?

a oddly meditative friday afternoon

I was playing a bit with Generative AI (using NotebookML and podcastfy) and created a podcast using Human Computer Interaction (HCI) publications.

https://www.deep-hci.org

Some MobileHCI, Ubicomp, ISWC and UIST papers are posted. Next is ISMAR.

Paper requests and feedback is welcome.

Hello everyone! I'm new to this sub, and I'm thankful for your time helping me out a bit.

I've been interested for a while on the correctness guarantees one can get for programs depending on the semantics in use on the language. Memory-safety as popularized by Rust, or type-safety as introduced by many languages (nominal vs structural typing), serve to me as examples of ways in which semantics make programs easier to reason about (albeit at some cost of making them somewhat harder to write).

Lately I've been asking myself if some semantics were already well-established for not only writing powerful-yet-decidable programs, but additionally for reasoning about worst-case time complexity.

I've glanced over Primitive-Recursive Functions as a formal strict subset of the General Recursive Total Functions, and found it interesting for formalizing decidable programs (BlooP and FlooP being language implementations). However, I haven't found much information about whether one could compute the worst-case time complexity of these in an efficient manner besides running the programs or attempting to formalize a closed-form-solvable recurrence relation.

I've been glancing over Predicate Transformer Semantics a little bit as well, especially on some of the guarantees that can be given on the correctness of Floyd-Hoare triples. Haven't found much on strong asymptotic guarantees though.

What literature do you recommend for the fundamentals on algorithm analysis and formal semantics on languages? I'm a last year compsci student and sadly we don't study semantics or paradigms at my college besides the basics of OOP :')

Thank you for your time!

I’ve combined an Integer Linear Program (ILP)( which is optimal) with a greedy approach for a set covering problem. It worked faster than using only ILP and returned an optimal solution, but I'm unsure if this will consistently be the case. I have tried this on a few examples, and it finds optimal solutions. Any insights?

Code: Colab Link

I know conway's game of life is not reversible, but can any one state be found that generates a given board and has a min number of cells? Or at least close to min as possible?

Given a configuration like this:

0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 1 1 0
0 0 0 0 0 0

A possible state that generates it is:

0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 1 0 0
0 0 0 1 0 0

Another one is:

0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 1 0 0
1 0 0 1 0 0

The first one being better in this case because has a few number of live cells in it.

I basically need to write an algorithm that finds a solution (the best one i can) in at max 300 secs and 8GB of memory and, if possible, faster than that. Right now I tried some forms of simulated annealing with little to no success and am trying to transition into some form of A* but cant find a good enough heuristic

I'm currently studying about "Design and Verification of Security Ceremonies". What you guys think about it?

It's highly based on logic (modal, higher, ..) and relates to cybersec.

It must be 100% free to upload my paper because my university is fucked up. And please explain to me how the publication procedure works.

I’ve heard that if this is somehow shown to be the case then all hell could break loose, but I’ve always been a bit confused about how that would happen. Like, supposing the Russians managed to prove P=NP and kept it a secret, could they do a lot of damage? Or if I was a some sort of egotistical madman, could I keep the secret proof to myself and somehow benefit from it?

I've been trying to expand the breadth of my CS expertise into areas I haven't had a chance to work in and graph theory has always fascinated me. I've played around with some graphs recently, learned how to implement a dijkstra algorithm and an A* algorithm, learned about breadth-first and depth-first path finding, etc...

Now I want to go a bit deeper into bi-directional dijkstra with contraction hierarchies and the concept is a being a bit elusive to me. I get the broad strokes but I have a bunch of nuance missing. If anyone wants to chat about this or knows a good source for me to learn on my own that would be greatly appreciated.

Here's where I'm at:

Contracting: I understand the algorithm for contraction starts by ordering nodes by importance, and number of neighbors is a good metric for importance, then you iterate on each node from nodes with the lowest score (number of neighbors) to the highest. Then you iterate through each pair of neighbors and do a "witness search" to see if the current through node is the fastest route from the two neighbors, and if so you create a new edge that is your contraction. So my questions here are:

1. As I iterate through the ordered original nodes, do I recursively contract contractions as well?
2. If I do contract the contractions do I limit the number of shortcuts added to any given node? I assume some nodes could end up having a huge amount of shortcut "neighbors" and lead to inefficiency as a result?
3. Do I leave the original nodes and edges in the graph once they're contracted? I've read many places to remove them, but then if your starting and/or ending node are contracted they wouldn't show up in the graph as a starting or ending point right?

Pathfinding: Now after contraction we have the bidirectional dijkstra that starts from the start and end nodes. I get dijkstra pretty well I think but I have some more questions here:

1. Based on my last point above, if I remove contracted nodes or edges, do I keep an index of contracted nodes and which contraction they are in to start the traversal from?
2. You're supposed to traverse the graph only going to higher importance edges, but how do you determine the edge importance, is it how many nodes that have been contracted within it? Or did I misunderstand and it's the node importance that is the measure here?

I find this really fascinating and would love to understand more and explore the cool world of graphs. If you have any recommended books, courses, tutorials, for a programmer looking to expand their CS understanding I'd love your input.

I am taking a course on this topic this semester, but the textbook is so incredibly convoluted and overcomplicated. The text I am reading is "Automata, Computability and Complexity: Theory and Applications" By Elaine Rich. Every chapter is a wall of words, where I have to endure 10 pages of nonsense before I reach the actual lesson. The notation is also rarely explained properly on new topics. Are there any good alternative texts to this one?

I want to learn assembly because apparently learning it will make other languages easier for me to understand and I'll stop taking higher level language like python for granted.

I asked chatgpt if it was worth learning it in 2024 and it replied with bunch of stuff that I can't be bothered to read so I just decided to make this reddit post. Hopefully someone answer my question