wtf

What's NPC? If you don't mind my saying, if you're an expert feel free to tell me to take a hike. But if you "watched a few YouTube videos" I suggest you'd greatly benefit from defining all your terms, summarizing exactly what it is you understand, and exactly what question you're asking. You'll probably answer your own question and/or uncover some uncertainties and gaps in your own understanding. The way you're talking about a few versus 1 nested loop shows you might be missing the essence of all this. A linear scaling factor doesn't make any difference to anything in the complexity business. X and a million times X are the exact same thing in this subject.

What are you talking about? A moment ago you were claiming there is an objective truth to whether full powersets exist. Now you're talking about something entirely different than makes no sense at all.

That doesn't make any sense. If you assume the powerset axiom then every set has a powerset that exists. If you reject the powerset axiom then there exists some set whose full powerset doesn't exist. It's not a matter of truth, it's a matter of which axiom you choose. There is no objective truth of the matter.

That's exactly what it means, by definition. Any set with the same cardinality as the naturals is countable. If it's strictly smaller it's finite. If it's strictly larger it's uncountable. That's all the word uncountable means.

I don't see it in this thread. Stop playing games. Post a proof or don't.

I read through this entire thread. You haven't presented any proof. Not even a sketch of an idea. What is there to discuss? Did I accidentally miss your proof?

Why?

That's a totally different conversation than the one I thought we were having. You said (unless I'm mistaken and someone else said this, in which case I apologize) that Collatz might be provable in some nonstandard model of the integers but not in the standard model. If that's what you said, I have to ask you why you believe that might be the case, and what second-order property might be involved. Collatz might well be undecidable. I hardly see how I'm "resisting" this possibility. We weren't even talking about it as far as I understood. I didn't go back to review the thread so perhaps I lost track of who was saying what at some point. Could we be using nonstandard in different ways? I'm thinking of the hyperreals, which is the "standard" nonstandard model of the reals if you think about it that way. But perhaps you just mean undecidable in the sense that the axioms don't decide the issue. That would make sense.

I see two problems here already. 1) The diagonal argument is NOT Cantor's theorem. There is no "list" in Cantor's theorem. Cantor's theorem says that any set has strictly smaller cardinality than its powerset. https://en.wikipedia.org/wiki/Cantor's_theorem. This is why you need to be more clear. 2) Neither Cantor's theorem nor his diagonal argument need to be framed as proofs by contradiction. The diagonal argument is a direct proof that any arbitrary list of reals is missing at least one real. Cantor's theorem is a direct proof that an arbitrary map from a set to its powerset fails to hit at least one set. Any complaints about proof by contradiction are misplaced here. > Does the power set of ℕ exist at all? Yes, by the axiom of powersets. https://en.wikipedia.org/wiki/Axiom_of_power_set > If it exists, its cardinality would be aleph 1 No, that depends on the Continuum hypothesis and is independent of the other axioms. The best we can say is that the powerset of [math]\mathbb N[/math] is [math]2^{\aleph_0}[/math]. But nobody knows which Aleph that is.

I was hoping you could educate me. You claimed that there might be a Collatz solution in a nonstandard model of the integers. I"m asking why you believe that. Trying to understand your earlier posts.

It's fascinating that although you can not trisect an arbitrary angle with compass and straightedge; you CAN trisect an arbitrary angle using origami. https://plus.maths.org/content/trisecting-angle-origami

I don't particularly need to read that article, since I know this proof very well and can reproduce it at will. It's so beautiful. One of my favorite proofs. What I think is missing here is evidence that YOU understand the proof. I know you can link it, but you haven't convinced me that you appreciate it. Until you say, "Aha line n of the proof is wrong because ..." you will have no credibility with me.

Can you say what aspect of this problem leads you to believe it might be true in some models and false in others, which means there could be no proof. As context let me give an example. Take the reals and the hyperreals. The hyperreals are a superset of the standard reals that include infinite and infinitesimal elements. It's a nonstandard model of the reals. Therefore it satisfies the same first-order properties and theorems tha the reals do. For instance. .999... = 1 in both the reals and the hyperreals, and the proof is identical in either case. This debunks a common theme in .999... crank threads, when people wrongly believe the hyperreals help them to falsify the equalty. They don't. But there IS an important property that the reals satisfy and that the hyperreals don't. And that is, metric completeness. The real line is complete. It has no "holes." The technical definition is that every Cauchy sequence converges. That means that every sequence that morally "should" converge, does converge. To illustrate this concept, consider the plain old rationals, the fractions n/m where n and m are integers. They are a field: You can add, subtract, multiply, and divide (except by zero of course). They are totally ordered: that is, for any two non-equal reals, one is larger than the other. The rationals are similar to the reals in the sense of being densely ordered fields. But the rationals are not complete. For example the Cauchy sequence 1, 1.4, 1.41, 1.412, ... consisting of more and more decimal places of the sqrt(2), "should" converge to sqrt(2). But it doesn't, because sqrt(2) isn't a rational number. So there's a "hole" in the rationals where the sqrt(2) should be. And we can express that without going outside the rationals by noting that there's a Cauchy sequence that doesn't converge. However, the hyperreals are not complete! It's a theorem that any model of the reals that contains infinitesimal elements can not be complete. There are Cauchy sequences that don't converge. There are holes. What happened? First I said that they share all first-order properties. But completeness is a second-order property. Another definition of completeness is the Least Upper Bound property, which says that a nonempty set of reals bounded above must have a least upper bound. This is the defining characteristic of the standard reals. And to express it we have to quantify not only individual real numbers, but over arbitrary nonempty SUBSETS of the real numbers. That makes the logic second-order; and the reals and the hyperreals may in fact differ on second-order properties. So -- sorry if that's a lot of words but I hope it's clear -- why is it that you think the Collatz problem has some aspect that makes it behave differently in some nonstandard models of the integers? What aspect of the problem necessarily creeps into second-order logic?

I'm a very experienced programmer. I've reviewed the contemporary language landscape and I believe Python is by far the best starter language. It's easy to get going and learn to do simple things. It teaches all the right concepts easily. It's a very clean-looking language. It can be used for serious things as long as they don't need to run too fast, so it can grow with your skill level. There are tons and I mean tons of free tutorials and MOOCs and websites and communities to learn from. Also it has this really cool command line interface that lets you try things out one line at a time. It's the ideal starter language. You should use Python 3, not Python 2. The community came out with a new version years ago and the adoption rate has been way slower than anyone imagined, so a lot of Python code out there is 2 and is incompatible with 3. That's on the Python developers, who got arrogant about how eager people would be to upgrade their major production systems to an incompatible version of the language, with no discernible benefit. Duh!! Bad stewardship.. But that's typical of the industry. Everyone truly thinks they're smarter and know better than everyone else, which leads to a lot of bad design. Anyway. Python 3 for you.

No direct knowledge but hard to believe. Any first-order statement has the same truth value in the standard or nonstandard integers, since they satisfy the exact same set of axioms. If the hyperreals or any nonstandard model of anything had produced any result of interest, we'd know about it. At best the proponents of the hyperreals claims pedagogical improvements in the teaching of calculus, but never a new research result.

Is that true? The network programmers know how to write clients and servers using the socket library. I don't think the IT admins know how to code at all. They know how to configure firewalls and such. My understanding from the places I worked. The admins can do a little shell scripting but that's about it. Programming's not a required skill for an IT admin, networking or not.

Ok I think this looks correct up to the part I quoted. Then comes this: > So how come using this proof we can show that any TM of the type X(n,m) = 1 or 0 doesn’t exist? How does that follow? I think the point is that we can't compute whether the n-th TM halts on input n. Whether it halts output some particular value doesn't seem to make a difference, if I'm following this. If you can't compute whether an arbitrary TM halts period, you can't compute whether it halts with output k for any k. Is that what you're saying?

It certainly hasn't been proven independent of the usual axioms. That would have made the news and it would be quite surprising. I think there's a quote from Erdős that math isn't ready for such problems, but he's referring to techniques, not axioms.

You're right, I didn't read the second version. If Penrose wrote it I'd say the same to him as I did to you. But then again he's Sir Roger so probably I wouldn't! I'll take a look at your latest exposition when I get a chance. I should mention (again) that I'm relatively weak on computability theory so if someone who actually knows this stuff wants to jump in that would be great. I'm not really the right person for this.

> Nope you can use state transition tables too https://en.m.wikipedia.org/wiki/State_transition_table I saw no syntax there that matched yours. Please supply a page describing your notation in detail. > Yes the halt statements are part of the input tape n they don't need to be there though. I left it there to show that you can use multiple state transitions on a tape. I don't know what that means. What are multiple state transitions on tape? The state transitions aren't on the tape in a TM. They're defined in the program. Where do you get the boolean expressions? Your program doesn't express any logic that I can see. > Who is everyone exactly? The CS community and all related communities such as physicists concerned with computability, mathematicians concerned with computability, philosophers, etc. And since the unsolvability of the Halting problem is intimately related to Gödel's incompleteness theorems. you have to overthrow modern mathematical logic too. And since Chaitin has proved incompleteness using complexity theory, there goes that too. You have a very large body of academic orthodoxy on the other side of your proposition. But that's not important. What's important is that I can't make heads or tails out of your notation. A TM consists of a program that acts on a tape one cell at a time. "If I'm in state X and the current symbol is Y then move the tape left or right, or leave it where it is, and optionally write the new symbols Z." I see none of that here. I didn't study CS so I don't know the details of DFA's so if you can dumb this down for me that would be great. I don't see anything being computed by your notation.

That's interesting because I feel exactly the same way. I don't want to be famous. I have no idea why so many people do. I know that your idea is wrong, simply based on the fact that everyone regards Turing's proof as perfectly valid. Modern computer science is based on his ideas. However as I indicated earlier, I'm not a CS expert. I know Turing's concepts and results, but I am not schooled in the technical details as a CS major major would learn them. I can't exactly see why your argument is wrong and can see I'd probably learn something from taking a run at it. I'll see if I can work through your idea this week. I'm a little busy with other projects at the moment but I'll put it in the queue. TO @Olfaction, I wanted to explain why I have trouble with your exposition. You can see that @fiveworlds has stated an argument that is so specific, that it invites step-by-step understanding so as to refute it. It's wrong -- almost certainly, because it contradicts a well-known standard result -- but it's specific. I can follow it step by step ... because there are steps! And in working through @fiveworlds's presentation, I'll probably learn something or at least set myself a fun puzzle. Whereas your exposition is handwavy. You say, "apply the same argument" but you don't say how to do it. You say that things are intuitively or clearly true, without presenting proof. It doesn't motivate me to work hard to understand you. I hope you will take this as constructive criticism. I am sure you have the kernel of some interesting idea, but you haven't provided enough detail for me to understand what your idea is. I encourage you to try to express your idea more clearly and succinctly. > :nextState(boolean function) @fiveworlds, Are the halt() statements underneath that line supposed to be indented? Are they part of the function definition? Also is this a notation you made up? Or is it a standard notation for TMs that I could read about somewhere, and if so where? * ps another question. In HALT() you say to output "I'm halted." But you didn't produce an output. For a TM to be considered to have halted, it has to halt after a finite number of steps and output some number. Formally it's helpful to think of TMs as functions from the naturals to the naturals. It inputs a natural number and it has to output one. In fact you seem to be missing the very computation that you are required to make. Could that be a flaw? Not sure yet, just trying to understand your idea. * ps -- another comment. Your program produces no output! You run it and it either halts or ends up in the stuck state (halting at an invalid state is regarded as not halting, in TM lore). Your function does nothing!! You run it and after a while it halts and outputs "I've halted," but it never computes anything at all! I think this is an aspect of your idea that needs to be fixed. You have to output a number. I mean you could just add the line "outout 47" to your HALT() function, but that's just the TM that computes the constant function 47. It certainly doesn't solve the halting problem. Help me out here, what is this notation supposed to do? * ps another question (the forum software will merge my replies anyway so I'll just stick them here): > :halt(input == toBin(":halt(true and not false)")) what are those inputs to the inner :halt? And if this suppose to be recursive, your :halt calls itself? With what arguments? What are true and false here? I think I'll stop asking any more questions till you clarify this notation.

If you could supply the details for how to do that you would become famous, since you'd falsify a proof published by Alan Turing in 1936 and taught to undergrad CS students to this day.

I prefer not to go through all that. Is that really Penrose's exposition? He's generally a very clear writer. In any event here's how I understand the proof. We enumerate all the TMs (there are lots of ways to do this, details are unimportant). We define a function H(n,m) that outputs 1 if the n-th TM halts on input m and 0 otherwise. We are interested in the restriction H(n, n). Note that H is definitely a function, we just don't yet know if it's computable. Assume there is a TM, call it TMH, that computes H(n,n). Define another TM, called TMx, as follows. TMx(k) first runs TMH(k) to determine H(k,k). If H(k,k) = 1, meaning that the k-th TM halts on k, then TMx(k) goes into an infinite loop. If H(k,k) = 0, meaning that the k-th TM fails to halt on k, then TMx(k) = 1. Now if TMx is in fact a Turing machine, it's on our list somewhere, say it's the x-th TM. What is TMx(x)? Well if H(x,x) = 1, meaning that TMH halts on x, then TMx goes into an infinite loop on x. But if H(x,x) = 0, meaning that TMH fails to halt on x, then TMx(x) = 1. So TMx halts on x if and only if it doesn't halt. That's a contradiction, showing that TMx can't exist. Therefore H is not in fact computable by a Turing machine. TMH can't exist. Now I admit I'm not an expert and I'm not familiar with all the variations on this proof. But the point is that in this version of the proof we define the hypothetical TMx, and show that it can't exist, showing that TMH can't exist. I'm asking you if you have an analogous construction for your idea.

From your OP: > Then we go through the same processes, using the diagonal slash, The fact that you refer to the proof of the noncomputability of the halting problem as the "diagonal slash" makes me think you don't understand the proof. I could be wrong but you are vague where precision is required. > it seems to me, we come to the same conclusion, that TMH* couldn’t exist! Have you an argument? > However, it seems from common sense that TMH* is perfectly computable, predictable and deterministic Likewise, "it seems from common sense" doesn't constitute a proof. You are missing all the details needed to have an argument here. The rest of your OP doesn't say anything meaningful. I don't want to pick on it sentence-by-sentence but if I got started at all that's where I'd end up. I honestly can't give constructive criticism because your post is all over the map and not particularly coherent. I urge you to take your argument to the next level of detail to help you sort out your thoughts. I don't doubt you have the kernel of some question in mind, I just don't know what it is. > Let say that instead of TMH, we have a TM that simply displays a ''0'' whenever a TM exceeds a fixed number of steps. Let’s term this Turing Machine TMH*. Then we go through the same processes, using the diagonal slash, and it seems to me, we come to the same conclusion, that TMH* couldn’t exist! Ok ps -- here is some specific constructive criticism. You recall in the proof of the unsolvability of the Halting problem, we assume we have a solver for H, called TMh; Then we defined some NEW Turing machine TMx, say, in terms of TMh, and then we diagonalize and show that TMx can't in fact be a TM at all. So in your scenario, we have TMh*. So what is your auxiliary function that you're using to get your impossibility result? In other words, "Then we go through the same processes ..." is where your argument has a giant hole. What same process? You need to be very specific.

Yes the Domino computer delivers! I gave the Wiki link but here's a direct link to a 19 minute video of a 10,000 domino computer that they set up on the floor of a huge gym or warehouse. (Annoying Youtube ad precedes, you can dismiss it in 5 seconds)