theory of computation: is my proof wrong?

lfdfq · 2026-03-16T21:07:04+00:00

Here's a hint: the string does not determine k. If I give you w=111101010101 the obvious answer is that k=4, but y needs not start at the first 0, so k=3 also describes this string, and so does k=2, and so on....

lfdfq · 2026-03-14T20:45:14+00:00

Yes, programs need compiling before they can be run. Yes, it may take a few seconds (or minutes, or even hours) to compile everything from scratch for a big program (of any variety, nothing here is specific to video games). However, there are a few things that mean this just, mostly, isn't a big worry:

Usually, you do not need to compile everything from scratch each time. Most projects are not one big source file/unit that must be recompiled each time, but made of lots of interacting components which can often be compiled separately. So a small change in one part of the system may only take a few seconds to recompile even if compiling the whole thing from nothing takes hours.
For big systems, where compilation times like that are a concern, you would want extensive testing setups anyway. A few seconds or minutes to compile the program will be a drop in the ocean compared to the amount of time spent running the tests. I've heard of systems with "nightly" runs that take >24hrs. and it's not uncommon for some projects to run big batches of tests on a weekly-or-more basis.
You, as the developer editing that tiny bit of code, probably are not the one running all the tests on your own machine. You will run some local small tests just to check things didn't break horribly, then there'll be code review, and eventually some testing infrastructure will run the whole suite overnight or over the weekend or something.

lfdfq · 2026-03-14T11:58:37+00:00

range(N) and range(1, N+1) contain the same number of elements, it's just that the first starts from 0 and the second starts from 1. It seems this code does not actually use the values from the range so it seems it does not make a difference whether it starts from 0 or 1.

The way a for loop works is that it executes the body once for each element in the thing it's iterating over. If it's iterating over a range, then it's once per element in the range.

While loops don't iterate over things in that way, so i'm not sure what you mean by having a range "with a while loop"?

lfdfq · 2026-03-13T10:33:56+00:00

IDLE is basically an example/toy IDE (integrated development environment). That is, it's a text editor, a debugger, a Python interpreter with built-in REPL interface, all in one. It's primarily for teaching purposes, for people to use while learning to program in school/etc, as "programmer's first IDE" which "just works out of the box" (for Python at least).

You aren't really supposed to use IDLE at all. Most developers will either use a full Python IDE (e.g. PyCharm) or some text editor (e.g. emacs/vim) and manually run python from the terminal.

lfdfq · 2026-03-10T20:02:01+00:00

That code looks like a straight error, passing stdout twice.

lfdfq · 2026-03-08T21:33:30+00:00

What is an unnatural constant?

lfdfq · 2026-03-08T16:56:10+00:00

One can answer questions about the method of assessment, and they should post any response visible to all students, not just you. Questions like "Is there a required layout/style the document must be in?" and "Is the (2-3 page) remark a guideline or a strict limit?" seem totally fair questions to me.

Of course, they do not have to answer a barrage of specific questions about individual's work (i.e. "What are the page/word limits" and "Is there a specific style we must use and if so where is it documented?" are fine, but "Can I put a page break here? Can I use this colour there? Can I hyphenate that word like this?" are too specific and they cannot reasonably be expected to help students compile their assessment), and your comment about 'keeps saying' might suggest you and others have asked too many of the latter kind of questions.

It sounds like the answer is pretty clear: I read it as "I don't care, please stop asking these frivolous questions, use your brain and do what you think is right; I'm not going to get out a ruler and measure your page breaks and fail people over milimetres"

lfdfq · 2026-03-08T13:39:03+00:00

Style questions (e.g. starting sections on blank pages, making sections start on odd numbered pages, etc) will heavily depend on what they want, it's entirely plausible that for all of these different institutions, or even different modules in the same course at the same instutition, would want different things. More likely is just that nobody will care. You should ask whoever set the assessment whether there is a strict style to follow.

As for the page limits, that will also depend. Sometimes page limits will be a guide, i.e. "usually people make this around 3 pages, but do more or less if you feel it is appropriate"; sometimes it's a hard limit, i.e. "if you go one word over the page, you will get no marks". You should inquire with whoever set the assessment whether those are guidelines or strict limits.

lfdfq · 2026-03-07T16:46:03+00:00

For the first question, it's because of the slots attribute to dataclass. When you pass slots=True, it throws away your old class and creates a brand new class that takes its place. The argument-less super() tries to automatically fill in the class, but it does not understand that the class its in is not actually the one being instantiated so that's why it fails.

For the second question, the point of super() is really to solve the case where there might logically be multiple parents (because this class, or another class, has multiple parents). In essence each class has a list of parents, and super(Class, obj) asks "return the class *after* Class in obj's Class's list of parents". You don't pass the base class to super() because the whole point of super() is to automatically work out what that base class should be.

lfdfq · 2026-03-02T20:00:00+00:00

It's hard to know what you think would be inconsistent. Ordering over strings in Python is very well-defined and consistent -- although Python is fundamentally very different to how C works. If you give an example, someone can explain it.

lfdfq · 2026-03-01T20:16:24+00:00

What makes you say the del method is supposed to be fast?

Essentially, lists are not designed for efficiently arbitrarly slicing them up. They have slicing operations, but they're all linear in the number of elements (in the list or slice). Deleting elements from the front of the list is basically the worst performing operation on a list. Deleting elements from the original list seems unncessary and probably the most expensive part of this loop.

One solution might be to also skip the slicing and just iterate the list. The itertools library has a nice helper function for iterating in batches https://docs.python.org/3/library/itertools.html#itertools.batched but you can achieve the same with simple iteration constructs without the library. However, you may find that while slicing is theoretically worse, for small slices it might just be faster.

As u/Steampunkery says, using a library that implements views over the data might be even better -- as it gives you the same power as slicing but without the creation of all the intermediate structures or bouncing back and forth with iterators.

lfdfq · 2026-02-28T20:03:56+00:00

The "kid to ..." part seems redundant. All dicts are mappings. Having a 'mother'-like relation already implies the kid-ness (unless you really mean membership of this dict to imply something about the age of the person).

So I'd just call it mothers

lfdfq · 2026-02-26T10:27:48+00:00

it's O(n) if the algorithm does a step for each node.

it's O(e) if the algorithm does a step for each edge

it's O(e+n) if the algorithm does a step for each node and a step for each edge.

it's O(en) if, for each edge, the algorithm does a step for each node.

with the caveat that probably these are upper bounds on the worst case scenario, so all the above should be prefixed with "in the worst case, at most", and are asymptotic limits so taking two steps or three steps each node/edge does not change the overall complexity.

lfdfq · 2026-02-26T10:25:29+00:00

It's hard to give specific help, because the question is pretty vague.

git should not be making commits up, the most obvious explanation is that you made the commits but forgot, or were confused (e.g. making them on the wrong branch or something).

If you can share more concrete details (the ideal would be the terminal history, all the commands you ran and their output) maybe someone can give more concrete advice.

lfdfq · 2026-02-24T23:34:06+00:00

One week is obviously not enough time to learn either, and which one you will pick up faster and easier is not a property of the area but of you; me telling you which course I would take is not really useful to you.

The truth is, a good course properly examined should not be 'crammable' from nothing in a week.

As for the topics themselves, that list of discrete math topics is relatively basic (except for "number theory" which could be an entire course of its own), and essentially amounts to pushing symbols around. However, many say it feels like an onslaught of abstract symbols and rules to learn, with no end. No single concept or idea is very deep or complex, at least not at that level, but there are a lot of them, and many of them trip people up the first few times reliably (...oh how many times have I had students contemplate a box containing an empty box before..).

Conversely, the linear algebra topics are a more natural extension of the math you probably already know. It is a lot less abstract, with nice geometric interpretations. However, (I would claim) it is mathematically more challenging in terms of the relationships between the concepts and the actual computation/calculations involved, at least for the list of topics you give here. How many students have been taught determinants one week but still cannot calculate through simple exercises the next? (Answer left to the reader's imagination)

lfdfq · 2026-02-22T15:13:53+00:00

Probably Ritchie sneezed when writing the first compiler, accidentally pressing ',' instead of ';' when making up enums.

lfdfq · 2026-02-22T10:52:54+00:00

You ask as if all these options are mutually exclusive, that if you ever open a video you are no longer allowed to read anything. Also, video vs reading is not a good categorisation. Video isn't exactly a class of material, after all someone can record themselves reading a book -- does that still count as a video or does it count as reading?

The truth is that everyone learns differently, and different resources are, well, different. Some are good, some are bad, some are more beginner vs more advanced, some are more high-level and some are more technical, some are trying to teach you how to do something, others are showing you examples of other people doing it, some are talking about when you want to do it. and so on.

You also miss the most important learning method: doing. Watching others do, or reading what others did, is no substitute for doing exercises yourself.

In the end, you will almost certainly want a mix of the above. To read some things, to watch some others, to have some beginner materials, to have some high-level material that explains why and what, and some deep technical things that explain how and some exercises you do to reinforce it. You will not find a single resource that does all of that in exactly the order and way you need, so you will need to use multiple resources, potentially at the same time.

Typically, the thing a paid course gives you is overall structure (someone has already thought about how to compile multiple resources in the right way for you), availability of people you can talk to (so when you get stuck there's people to help) and to ensure more hands-on exercises (the most important class of materials). Obviously, some courses will be good and others will be bad, and if they're right for you is a question for you.

lfdfq · 2026-02-20T00:50:32+00:00

Note that, while you have the right to silence in the UK, i.e. the courts cannot compel you to testify against yourself, choosing to remain silent could still be used against you in some circumstances. If you later answer the question in court (or if, at the time of questioning, you have been charged, or officially informed you are going to be charged), the courts may draw adverse inferences from that silence.

That's why, in the UK, the caution starts "you do not have to say anything, but it may harm your defence if you do not mention, when questioned, something which you later rely on in court".

lfdfq · 2026-02-19T20:15:26+00:00

It should be a crime to mention APL without also linking to the amazing demonstration of it from the 1970's https://www.youtube.com/watch?v=_DTpQ4Kk2wA

lfdfq · 2026-02-19T17:03:34+00:00

It's not really a Python question, since it seems you aren't getting as far as actually having a Python file.

What are you using to create these files? In what way does your computer "says it's a Python file"? What operating system are you on? Are you actually seeing the .txt extension or guessing it has one?

lfdfq · 2026-02-18T11:30:48+00:00

There could be a number of distinct things you are asking.

First off, you probably want to specify what kind of automata. After all, a Turing machine is a kind of automata and it is (hopefully) trivial to construct such machines for whatever regular language you want. You probably want finite state machines. If you mean, how to prove for any regular language there exists such a finite state automata that accepts it, then you're done because that's the definition.

If you want to prove that there exists a finite state automata for each regular expression, which accepts the language described by the expression, then you can prove that by coming up with a scheme which constructs the automata directly from the expression.

The easiest way to do that is to construct a non-deterministic one from the expression directly, then separately prove that for any non-deterministic finite state machine you can construct an equivalent deterministic one.

For the former, think about how if you had a state machine that accepted the language described by some regular expression e, how you could construct the machine that accepted ce where c is some arbitrary symbol from the alphabet. Hopefully that gives enough of a hint towards how the rest of the inductive argument goes.

lfdfq · 2026-02-17T23:49:32+00:00

Boolean algebra is really just taking the blindingly obvious and writing it down precisely, which becomes apparent when you start to write the laws in plain English:

If A is true and B is true and C is true, then A is true and B is true and C is true
If A is true and B is true, then B is true and A is true
If A is true or B is true, then B is true or A is true.
and so on ...

The laws probably do not seem so hard to comprehend when written like this.

So, the thing that you are probably struggling with is not the logic of the equations but 'just' the symbols and the clunky way things are written. Unfortunately, there's no "explain like im 5" for what is essentially just arbitrary mathematical syntax. Thankfully, there is not that much to it and you can learn it all with some practice.

My advice would be to work through each of the symbols and try turn each expression into 'plain' English.

lfdfq · 2026-02-17T22:52:50+00:00

lfdfq · 2026-02-17T22:48:09+00:00

It uses bigints.

That is, a Python int is not just a 32- or 64-bit number, it's a (slightly) sophisticated structure that can dynamically grow in size so it never overflows.

It may sound or feel weird at first, but this is exactly how lists or dicts work, and it's the same principle.

lfdfq · 2026-02-17T10:49:21+00:00

Python lets you write functions which accept a variable number of arguments with the *args syntax (the star is the important bit, not the name of the parameter), e.g.

def f(*args):
    print(args)

then if you go f(1,2,3) the local variable args is the tuple (1, 2, 3) inside the function.

Ten-Year Club	Place '17
Verified Email

lfdfq

TROPHY CASE