From 3.5 billion Reddit comments

14 points

·
19th May 2019

Google hasn't been helpful because no such algorithm exists. Check out Rice's Theorem for the impossibility.

edit:

Let S be the set of languages that you can reduce SAT to in polynomial time.

SAT is clearly in S, and we know some machine recognizes it.

The empty language is not in S (even if P=NP, so that SAT is P-complete), and we know some machine recognizes it.

By Rice's Theorem, no machine decides, when given a machine as input, whether that machine recognizes a language in S.

(we assume that the "any custom problem" input is as a machine encoding)

edit2:

I see that you make a lot of questions about computational complexity, but do not have a good foundation. Many things you propose or ask already have known impossibility results. May I suggest you have a look at Sipser (https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X)? That will give you a better understanding of computability and complexity to understand the feedback you're getting.

5 points

·
25th Mar 2019

You'll find 251 much closer to 127 than 112/122, but I'd hesitate to make comparisons between those courses. Just very different material overall. I think typical CS first-years will spend about three to four days per week outside of class on 251, but part of that is not knowing how to study and not making good use of office hours.

Might describe it as taking two 127's simultaneously, or three on a particularly bad week, but that's my opinion.

If you're the type that's inclined to read ahead, Sipser is available in the library and prepares you fairly well.

2 points

·
23rd Jan 2021

One of the best math books ever written imo (and yes it is very much a *math* book):

<strong>Introduction to the Theory of Computation</strong>

(If cost is an issue then the previous addition used is great and almost the same; and there’s online if you still can’t do that.)

The book is very rare in that it separates math proofs into **proof ideas** and **proofs with details**. This seems like a natural thing to do if you’ve ever done proof-based math and it is, but it’s also rare.

It’s the most comprehensible math book that is also a very serious math book.

The things it deals with are also really *interesting* on their own. A lot of math is hard to appreciate without a large context of math. But Comp *Theory* is discusses things that have immediate philosophical and intellectual meat 🍖 on them (like what questions can be asked - impact of determinism vs probability on reasoning - what can simple automata recognize). It’s basically mathematical epistemology (theory of knowledge).

For me: I didn’t really enjoy math until I took a discrete, proof based math class. Calculus and such require precision and there’s some intuition there — but it often feels more like tools than goals means than ends. Which, for me, wasn’t as exciting.

I’d definitely give this book a look if you’re interested in developing analytical and problem solving skills.

**TLDR**: not an algorithms book - a proof based ~theory of what can be known math book. That is very serious, but remarkably accessible.

1 point

·
16th Mar 2022

>Generally understood, computation is processing math formulas.

Please, for the love of god, go read an introductory book on computational theory. Or here, read this page on Automata theory, which is a major part of computational theory. You'll find that there is very little maths formulas or numbers in there.

You're confidently asserting about things you know nothing about.

1 point

·
14th Sep 2021

This is one of my favorite math books, hands down. And among the best written and most accessible.

Introduction to the Theory of Computation - Michael Sipser

If you’re interested in theoretical cs I recommend reading through it.

Broadly: theoretical computer science is like epistemology with substance. It’s a study of *what* can be known.

Even questions of “speed” are about speed classes so vastly different that they are effectively about what is knowable.

1 point

·
20th Sep 2020

If you want to start from state machines and build your way to general regular languages. It really helped me fully understand the *how* behind regular expressions.

1 point

·
10th Mar 2020

I'm currently at the tail end of my computer science degree and have been taking a Theory of Computation class. Our book has been a really great resource the entire semester and it's made the class very interesting!

Here's the link to it on Amazon but I did find it for free online in PDF form :)

https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X

1 point

·
22nd Feb 2017

Can I say Sipser's Introduction to the Theory of Computation? I know there are issues people have with the book, but in terms of accessibility and ease of reading, I think this text is second to none. I mean, though it says in the preface it's designed for upper-level undergraduates or fresh grad students, it makes no assumptions on the reader's level of knowledge, and as such I would feel comfortable recommending it even to some high school students.

1 point

·
9th Jul 2016

>If you want to go more theoretical, look into set theory, regular languages, automata and state machines.

Sipser covers these with a theoretical-leaning book: https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X

1 point

·
9th Dec 2015

From deleted twitter account

Dr_Craig_Wright twitted at 2015-05-10 02:06:51.000:

For those who wonder just how far you can "push" the scripting language in Bitcoin... http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X

1 point

·
23rd Aug 2015

Just to add to the points, the Sipser book has been recommended by many if you ever have trouble understanding the required texts. I didn't take the course with Bachmair, but the text has been recommended by his students as well.

1 point

·
12th Jan 2015

Introduction to the Theory of Computation by Michael Sipser: http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X

Edit: wow, that book is more expensive than I remember. I have the 2nd edition, which can be found for a fraction of the price of the latest new edition. I'm not sure how they compare in content, though.

2 points

·
4th Oct 2020

Abelson and Sussman's famous SICP book plus Michael Sipser's Intro to the Theory of Computation will get you pretty far.

However, truly understanding an industrial-strength programming language inevitably requires time and experience. It's not just a matter of knowing the language rules and features. You have to understand how the features are directed, in an engineering context, toward well-organized, structured software. As with human languages, you have to learn the idioms and become familiar with the community of speakers.

1 point

·
15th May 2022

Here is the sequence I recommend for learning how to write mathematical proofs:

- Start with an introductory textbook. <em>Book of Proof</em> by Hammack is a good one (and available for free). <em>How to Prove It</em> by Daniel Velleman is also a good choice.
- I also recommend that you supplement your textbook readings with video lectures, such as this one from Mike Pawliuk.
- Learn how to use a formal proof assistant. Coq and Agda are the most popular. Both allow you to write a proof as a program instead of as a paper, and provide various tools for formally checking your proof.

That will give you a good foundation, but its not the end. Writing proofs is a skill that must be developed through practice, and the best way to find further practice is to dive into more advanced mathematical topics. The usual next steps for students are introductions to abstract algebra and real analysis. Since you are a programmer you might also be interested in something like <em>Introduction to the Theory of Computation</em> by Sipser. Alternatively, instead of more studying you could go through old math olympiad and Art of Problem solving problems. Another resource is Proofwiki; breaking down and analyzing others' proofs can be good practice in itself.

1 point

·
31st Jul 2019

It's Problem 7.29 in the third edition of Michael Sipser's Introduction to the Theory of Computation (you can find it by searching for "coloring" when using the preview function on Amazon). It's also in The design and analysis of computer algorithms by Aho, Hopcroft and Ullman as Theorem 10.12, though the proof seems different from what you've sketched). (I hope that the Google Books link works. Sometimes it won't show the right preview.)

1 point

·
21st Oct 2020

> To me it just sounds like all the other stuff isn’t really “ML” at its core.

All of that data acquisition and preprocessing isn't actually ML, but it's stuff that you'll likely have to do in the workplace. In my experience, nearly all data scientists have to engage in at least some data engineering, and sometimes it ends up being the major work item in a project.

Algorithms as a subject of study in their own right are important in ML itself in two ways. First, understanding and selecting the ML algorithms you'll use requires the ability to read and analyze those algorithms. HCA vs k-means, rmsprop vs adadelta vs NAG etc. K-means is usually more efficient, rmsprop usually converges faster. Still, about one project in three has the "standard" choice as non-optimal. Analyzing the algorithms allows you to understand these cases, why they happen, and be able to select the best algorithm for your current case. The second major way is in designing and implementing ML algorithms yourself. What if you need to get your ML system running in an environment where you can't use your statistical library of choice? What if you want to use an algorithm that hasn't yet been implemented in that package?

> Do you know how a stat/math background person can get some experience with this other side? Currently my knowledge of Python is limited to using pandas, sklearn,numpy, keras/TF etc to analyze a dataset one off. I don’t really know Python without those libraries. Eg loading a CSV without pandas looked very complicated

For understanding algos and data structures, *Introduction to the Theory of Computation* and *Introduction to Algorithms* will provide everything you need to know. Combine those with some YouTube, Khan Academy, or Coursera and you'll have the key theoretical knowledge.

Then it's just a matter of practicing. Use W3schools, try to implement some ML algos yourself, etc. Write a web scraper to get data from the US Census Bureau and FBI to feed into ML models predicting crime rate changes, or perhaps grab census and economic data to analyze changes in poverty/prosperity in each region of the US. Analyze the efficiency of the algorithms you used, and ask yourselves if there's a way to make it run more quickly. Always try to have a project going that's just a little bit past your current skill level.

CS skills and knowledge separates data scientists from data analysts, just like statistical skills and knowledge separates them from SWEs.

1 point

·
25th Feb 2018

Oh my god you're a fucking moron. Did you even read my comment? If you are discussing theory and this is your reply to my comment, you have a fundamental misunderstanding of the theory. The other explanation is you read something incorrectly, which wouldn't be such a problem but then you adopt such a cunt tone in your reply.

In **theory**

>Anything that can be done with a regex can be done with a finite automaton, and vice versa

*Where did I state that recognising an email is impossible with finite automata?* If something can be recognised by a finite automaton, it can be done with a regex.

Your original comment said that you cannot do this with regex but can with finite automata, but in **theory**

>They are equivalent in their expressive power, they both recognise the set of regular languages.

Anybody who has a semblance of an idea of what they're talking about will agree that they are **in theory** equivalent. So you *can* do it with regex, in **theory**.

Your article that you linked but didn't read carefully, states this same fact.

>And can you fully implement the complex grammars in the RFCs in your regex parser in a readable way?

It talks about the *practical* issues, e.g. being able to do it in a readable way with regex, because **in fucking theory** they are equivalent in their expressive power.

You may find the below useful:

https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X

Alternatively:

1 point

·
12th Apr 2017

Another one that's more hardcore EE than computer science is The Mathematical Theory of Communication. Shannon's 1948 paper this book highlights is the foundation of information theory.

1 point

·
23rd Apr 2017

OK,

https://mitpress.mit.edu/books/introduction-algorithms

get an old version: https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X

try out hackerrank challenges

1 point

·
19th Sep 2016

1 point

·
18th Apr 2016

If you're starting from scratch scratch I know the feeling very well.

I like these resources:

Just a [long, long] blog article http://steve-yegge.blogspot.com/2007/06/rich-programmer-food.html

A very cursory introduction to interpreters and the parts of programming languages with worked exercises https://ruslanspivak.com/lsbasi-part1/

A popular textbook that covers automata http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X (also available online if you poke around etc.)

When you're teaching yourself it is hard to know when you have gotten "enough" of preliminary topics and move on. Sometimes it is a good idea to identify the learning resource you "really want" to be getting to and to check in periodically while you're slogging through prerequisites so you can gauge whether you're there yet.

If you haven't been through SICP, I would say that is the best fit for you based on the limited information provided here. It is a guided journey that leads to building a simple language language.

http://sarabander.github.io/sicp/html/index.xhtml http://icampustutor.csail.mit.edu/6.001-public/

1 point

·
15th Jun 2015

Introduction to the Theory of Computation by Sipser http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/ref=sr_1_1?ie=UTF8&qid=1434343859&sr=8-1&keywords=Theory+of+computation

1 point

·
14th May 2015

Sipser is good as an introduction to both complexity and computation. Arora and Barak is also good for a stronger focus on complexity.

< $50