Search found 250 matches

Fri Dec 29, 2017 3:40 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)? Start with left_side(k) = right_side(k) You know this is true for at least one k. (That was your first step.) Now write left_side(k+1) =? right_side(k+1) You don't know this is true yet. The object...
Fri Dec 29, 2017 2:15 am UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

So Devious, in order for my explanation to work, must (in addition to taking itself as an argument, which I'll call Devious-as-argument) contain a copy of Oracle's code so that it can--when it takes itself as an argument--feed Oracle to Devious-as-argument? Do I have that right? Almost. Devious con...
Thu Dec 28, 2017 10:41 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

then runs Oracle on Devious. That's a shorthand way of saying "Devious contains a copy of Oracle's routines, and it feeds the input into those routines to see what Oracle would have said". In this case the input is the copy of Devious. So, its copy of Oracle's routines analyse Devious and...
Thu Dec 28, 2017 9:19 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

But, somehow, the Devious-as-argument-to-Devious gets Oracle to run (I don't know how this happens). Devious contains (a copy of) the code for Oracle within it. Devious is essentially Oracle with its outputs reversed. We feed a copy of Devious to itself as input. Devious "asks" its built-...
Thu Dec 28, 2017 8:11 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Returning to this after some months away to be sure that I understand the proof sufficiently. Any help would be appreciated. Here's my high-level understanding of the proof: We pretend that a program Oracle exists such that, for any program (P) with input (i), Oracle will tell us whether P halts whe...
Wed May 10, 2017 5:58 pm UTC
Forum: Coding
Topic: Basic Question Involving Functions (Python)
Replies: 18
Views: 11506

Re: Basic Question Involving Functions (Python)

I'm trying to learn a programming language, and after some research decided to explore Python. Given the conceptual difficulties that you've had in your Mathematics threads http://forums.xkcd.com/viewtopic.php?f=17&t=122713 and http://forums.xkcd.com/viewtopic.php?f=17&t=122712 I really don...
Sun May 07, 2017 6:10 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Great! I think I may have (at least) a high-level understanding of both versions of the proof-by-contradiction. Let me summarize what I understand both of them to be and y'all can tell if each summary is good enough for our purposes. Thanks again to all of those who've helped me in this thread; I re...
Sun May 07, 2017 12:53 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

If you find function notation to be beyond your grasp, it's a good bet you don't really understand how substitution actually works, which seems to be evident from your posts in this thread. In that case, you are naturally going to have a tough time understanding what "the k+1 case" even m...
Sun May 07, 2017 12:28 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

The internal Oracle (that Devious uses) proclaims something. Acting upon its unknown but claimed-perfect mechanism for working out what D(D) does. Devious then acts upon this information, via its legitimate coding, to do make the actual D(D) do the opposite. Game over. So that's why the opening mov...
Sun May 07, 2017 11:30 am UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Let me explain what I (think that I) get and everyone can fill in the gaps. Thanks to all for their help so far. We have a program called Oracle. Oracle, we say, must do two things: (1) it must itself halt and (2) it must tell us (correctly) if any arbitrary program P will halt when that program (P...
Sun May 07, 2017 1:45 am UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Let me explain what I (think that I) get and everyone can fill in the gaps. Thanks to all for their help so far. We have a program called Oracle. Oracle, we say, must do two things: (1) it must itself halt and (2) it must tell us (correctly) if any arbitrary program P will halt when that program (P)...
Sat May 06, 2017 10:23 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

Demki wrote:Yes, basically. What you want is simply to derive the (n=k+1) case given the (n=k) case, as has been done in the proof you've given, along with a base case.

Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)?
Sat May 06, 2017 10:05 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

It's not, it is just written differently, and is missing a base case. OK. I have some vague notion that, in solving the original question, I don't want the left-hand side to look the same as the right-hand side. Instead, I want to manipulate the right-hand side to look like something else. Is that ...
Sat May 06, 2017 9:45 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

I've spent some time thinking about induction, and I've figured out that I don't have the algebra skills to complete any induction problem right now. I simply don't know the re-writing rules well enough to perform the symbol-magic to get at a solution. Nevertheless, can someone tell me why the proof...
Sat May 06, 2017 9:24 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Ok, imagine a box that adds two numbers. It has two doors in, and one door out. If a three and a five go in, an eight comes out. And note also that a copy of a three is just as good as an "actual" three. (Copy boxes are on sale at Staples). Imagine another box, that doubles a number. If a...
Sat May 06, 2017 9:16 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Every complex program has smaller parts inside it, and part of Devious is Oracle. If you think of them written in some programming language, then Devious is just the same program as Oracle, but with a few lines of code before and after all the lines of Oracle. So why do we distinguish between argum...
Sat May 06, 2017 9:14 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Consider a program double() that doubles a number (and has one input), and another program add() that adds two numbers (and thus, has two inputs). If double() is implemented using add(), it simply feeds the same input twice to add. double(input) { result=add(input, input); . output(result); } Same ...
Sat May 06, 2017 6:53 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Big post, but I wanted to take a crack at explaining this and clearing up some of your problems. Let me know if and when something confuses you. This is a helpful attempt - thank you. One thing to note is that programs by their very nature are required to give the same output when fed the same inpu...
Sat May 06, 2017 1:53 am UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

I've spent the past couple of days thinking about this problem. What I'm still confused about are the different levels of programs, input, etc. When Oracle is running within Devious, how can we say that Oracle decides (or doesn't) decide anything about Devious (at the outermost level) will or won't ...
Wed May 03, 2017 5:11 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

Right, exactly. You're correct that if we take "odd" to mean "not even", then there's nothing to prove. But under the standard definition about 2m and 2m+1, it takes a little bit of justification. Clearly, if I take 2m and add 1, then I've got 2m+1 which is odd. But what if I ta...
Wed May 03, 2017 4:39 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

Yes! That is a valid argument, and a perfect example of proof by induction. You have the base step, the induction step, and you correctly justify your conclusion using known properties of even and odd numbers. But my argument still contains an assumption that I'd need to build out (I think), which ...
Wed May 03, 2017 4:31 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

Yes! That is a valid argument, and a perfect example of proof by induction. You have the base step, the induction step, and you correctly justify your conclusion using known properties of even and odd numbers. But my argument still contains an assumption that I'd need to build out (I think), which ...
Wed May 03, 2017 4:06 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

The first sentence you wrote just reiterates the definition of an even number. You gave no justification for why every integer that isn't even to be odd, since odd means 1 greater than an even number. The proof by induction provides such justification. I have to start somewhere. By necessity, becau...
Wed May 03, 2017 3:41 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

The first sentence you wrote just reiterates the definition of an even number. You gave no justification for why every integer that isn't even to be odd, since odd means 1 greater than an even number. The proof by induction provides such justification. I have to start somewhere. By necessity, becau...
Wed May 03, 2017 3:26 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Yeah, the main similarity is that they're both proofs by contradiction. Another similarity, which is common in many nonexistence proofs, is that we get the contradiction by looking at one proposed solution and showing that it isn't really a solution. Then we notice or show that the argument doesn't...
Wed May 03, 2017 3:21 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

What background knowledge? Do you have some other proof that every integer is either even or odd? Remember that "n is even" means "there exists m such that n=2m" and "n is odd" means "there exists m such that n=2m+1" Did you ever prove the statement "eve...
Wed May 03, 2017 3:00 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

It's pedagogically useful. It is nice to practice proof by induction if you do not understand induction by using it to prove things which you can already understand and prove by another means. I would agree with that, but the problem with the even-odd example is that it doesn't (at least in my view...
Wed May 03, 2017 2:49 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

It's pedagogically useful. It is nice to practice proof by induction if you do not understand induction by using it to prove things which you can already understand and prove by another means. I would agree with that, but the problem with the even-odd example is that it doesn't (at least in my view...
Wed May 03, 2017 2:29 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

Fun fact: the top answer to the question "how to prove that every integer is either even or odd" on math stackexchange is proof by induction. https://math.stackexchange.com/questions/1402679/proving-that-all-integers-are-even-or-odd I recognize that such a proof is possible (various folks...
Wed May 03, 2017 2:07 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Well more broadly we can use it to prove that no program can be a halting oracle, because any alleged oracle is susceptible the same proof. Also, there are many other things that we can prove by contradiction, by showing that something would imply the existence of a halting oracle. It seems like th...
Wed May 03, 2017 1:42 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Pretty much, yes. Gotcha. So the halting problem isn't particularly intellectually interesting but for the fact that it shows that there's at least one program about which Oracle cannot (by definition or design) make a correct prediction as to whether that program will halt or not - do I have that ...
Wed May 03, 2017 12:56 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

What do you mean, "How can it be?" We've already given many examples of things that look at other things' outputs. Sure, we're sort of tricking Oracle into making a false statement, but there's nothing illegal about that. It's the same thing we'd to with someone who claimed to be able to ...
Wed May 03, 2017 12:52 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

MathDoofus, you are writing an enormous amount of posts in two very active threads on two rather different topics. Personally, I don't know if you're taking the time to take everything that's being said to you and process it. You can, of course, continue in this manner, but my suggestion to you is ...
Wed May 03, 2017 12:07 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

Demki, your example is a good one, and may sidestep issues about "or" statements in proofs. I am far too invested in the original problem to drop it. Although I appreciate that others are trying to direct me to alternative problems, I do not yet have the instincts or insight to be able to...
Wed May 03, 2017 11:46 am UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Beyond all the notation, which I find too difficult to follow, how can it be that the Devious program is permitted to examine Oracle's result and do the opposite? How does that show anything meaningful about whether Oracle is right in the sense that normal people might use the concept?
Wed May 03, 2017 2:04 am UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

What is either program going to do without any arguments? Oracle tells us what a particular program does when given a particular input . It needs both of those arguments in order to do anything at all . Devious responds to what Oracle tells us the program corresponding to the one argument for Devio...
Wed May 03, 2017 1:53 am UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Oracle is part of the Devious program. A program that takes an input and divides that input by three doesn't need three as an argument, because the three is always part of that program. Similarly, Devious checks what Oracle says about its input. It doesn't need Oracle as an argument, because Oracle...
Wed May 03, 2017 1:50 am UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 257
Views: 45192

Re: Mathematical Induction - Introductory Question

After having proved that the formula is valid for all n, you can replace n with k+1. If you do that, you get sum to k+1 = (k+1)(k+2)/2 At which step do I "prove[ ] that the formula is valid for all n"? I'm confused by that statement. Please - can someone tell me directly what comes after ...
Wed May 03, 2017 1:47 am UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 44588

Re: Halting Problem

Oracle is already part of Devious, by definition. As in, that's how we defined Devious. How can Devious make Oracle do anything if Devious isn't taking Oracle as an argument? If arguments don't matter, then why do we go to pains to emphasize that Oracle takes two arguments, one of which is a progra...
Wed May 03, 2017 1:38 am UTC
Forum: Coding
Topic: Basic Question Involving Functions (Python)
Replies: 18
Views: 11506

Re: Basic Question Involving Functions (Python)

Since you're a total beginner, I recommend steering away from most Python tutorials; they'll generally be teaching you Python itself, and assume you already have basic knowledge of how programming itself works. There's a big list of Python-related "I'm totally new to this whole programming non...