Search found 245 matches

Wed May 10, 2017 5:58 pm UTC
Forum: Coding
Topic: Basic Question Involving Functions (Python)
Replies: 18
Views: 2582

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: 200
Views: 6317

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: 252
Views: 5704

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: 200
Views: 6317

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: 200
Views: 6317

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: 200
Views: 6317

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: 252
Views: 5704

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: 252
Views: 5704

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: 252
Views: 5704

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: 200
Views: 6317

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: 200
Views: 6317

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: 200
Views: 6317

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: 200
Views: 6317

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: 200
Views: 6317

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: 252
Views: 5704

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: 252
Views: 5704

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: 252
Views: 5704

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: 252
Views: 5704

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: 252
Views: 5704

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: 200
Views: 6317

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: 252
Views: 5704

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: 252
Views: 5704

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: 252
Views: 5704

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: 252
Views: 5704

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: 200
Views: 6317

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: 200
Views: 6317

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: 200
Views: 6317

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: 252
Views: 5704

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: 252
Views: 5704

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: 200
Views: 6317

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: 200
Views: 6317

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: 200
Views: 6317

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: 252
Views: 5704

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: 200
Views: 6317

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: 2582

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...
Wed May 03, 2017 1:37 am UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 200
Views: 6317

Re: Halting Problem

gmalivuk wrote:Devious takes one argument, but to get the contradiction, the argument it takes is (the number corresponding to) Devious itself, not Oracle.

OK. So Devious takes only one argument (a program, Devious). How does Oracle get into the picture if Devious takes only one argument?
Wed May 03, 2017 12:25 am UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 200
Views: 6317

Re: Halting Problem

Almost! There's one part where I'm unclear what you're referring to, so let's clear that up: Here, we design a world in which we have Devious call Oracle as its sole argument. It sounds like you're saying here that Devious takes Oracle as its sole argument. Is this what you meant? If so, then this ...
Tue May 02, 2017 11:58 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 252
Views: 5704

Re: Mathematical Induction - Introductory Question

Unfortunately, the algebra steps are (mostly) too small to be legible Do you mean conceptually? :P Because you can click the image for a full resolution version that you can read ...and you can click the full resolution image again to zoom it to actual scale, assuming you don't have an expensive ul...
Tue May 02, 2017 11:48 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 200
Views: 6317

Re: Halting Problem

I dunno. Here's the steps again: * The Devious machine is large, and contains an Oracle machine inside of itself. * The Devious machine expects to be fed a box of parts. It'll then either explode, or print a smiley face. * It does this by feeding that box of parts to its internal Oracle machine. * ...
Tue May 02, 2017 11:46 pm UTC
Forum: Mathematics
Topic: Mathematical Induction - Introductory Question
Replies: 252
Views: 5704

Re: Mathematical Induction - Introductory Question

If you want to continue down the even-or-odd induction proof path, then please (for my sanity) explain, using the contents and steps of that even-or-odd proof, how each piece of content and each step from that proof relates to if/then statements and the steps of the original induction proof that I'...

Go to advanced search