-D30, M11, Y14-
Hello. So I have been painstakingly attempting to comprehend and apply the halting function to another uncomputable function via reduction, where you define the uncomputable function within the halting function to show that said uncomputable function is in fact uncomputable.
<<about 3 hours later>>
Alright, I think I managed to apply successfully. It seems that these type of not computable functions hold to similar structures: they return only boolean or they return some other output that never changes--such as the number 42. Only then does it seem that the halting function can be (presumably) defined by these functions, and since we know that the halting function is not computable, it is safe to say that the function of interest which was utilized to define the halting function, cannot be computable either.
Now, aside from this, we were briefly introduced to the idea of induction. Although this is a topic in Calculus courses, the steps by which computer science induction is completed has a key difference: you begin with the induction hypothesis, prove it with the induction step, and then determine the base case(s). Although this course makes heavier use of mathematical expressions than Calculus, I do not see how induction problems in this course can so differ from induction problems in Calculus is they are the same thing. The first replaces language with their mathematical equivalents, whilst the second retains the language.
However, the induction problems in this course do bear a striking resemblance to big-Oh and big-Omega proofs, and those are definitely easier to prove when one goes through and proves it and then determines what elements (c and B) were necessary for the now complete proof to work.
It sounds suspiciously similar to circular reasoning, in my opinion, but that is a discussion for a later time. Thank you for reading this conclusion to Mathematical Expressions and Reasoning.
