Zgarb

general recent conversations

Discussion on question by polcott: Co…

Imported from a comment discussion on cs.stackexchange.com/que...

Zgarb

Dec 19, 2021 20:41

Let us continue this discussion in chat.

Zgarb

Dec 19, 2021 20:41

"A SHD always halts." This still confuses me. Returning to my earlier comment: how does H((u32)F, x) halt, if the simulated computation F(x) never halts and never enters an infinite loop/recursion that H could recognize? Is H an SHD or not?

Zgarb

Dec 19, 2021 20:41

Ok, that clears up the role of H. Now, what would be the result of running P((u32)P) in the main function? Would that computation halt?

Zgarb

Dec 19, 2021 20:41

I'm having trouble understanding "simulating halt deciders." Suppose we have an SHD H, a function F and an input x, and F(x) never halts and never produces the "simple cases of infinite recursion and infinite loops" that H can recognize. Does H((u32)F, x) return a value at some point, or does it keep simulating F(x) indefinitely?

Zgarb

Dec 19, 2021 20:41

I'm still confused by two sentences. 1) "Simulating halt deciders must abort their simulation of all inputs where the pure simulation of this input would never halt." This seems to imply that an SHD always halts. 2) "This allows simulating halt deciders to totally ignore their own behavior in making their halt status decision." What does this mean?

Zgarb

Dec 19, 2021 20:41

I'm not familiar with C. What is (u32)P?

Discussion between Ilkka Törmä and po…

Imported from a comment discussion on cs.stackexchange.com/que...

Zgarb

Jul 10, 2021 05:42

You are basically promising H that the never-halting checks of H will not find a loop or infinite recursion. But that promise is not guaranteed to be true.

Zgarb

Jul 10, 2021 05:35

@polcott It seems to answer the slightly different question: "Would input 1 halt on input 2 if H never aborted its simulation?" If H aborts its simulation of P(P) based on the assumption that the simulated H won't abort P(P), then either that assumption or the decision to abort is incorrect.

Zgarb

Jul 9, 2021 23:52

@polcott The issue is that if H ignores parts of the simulated execution trace when it checks for never-halting behavior, it might not be a pure simulator.

Zgarb

Jul 9, 2021 23:05

H is essentially a simulator that doesn't simulate the input program, but a modified program in which every call H(F,x) has been replaced by H2(F,x), where H2 is like H but without all the checks for non-halting. But then it can't be used to argue about the halting status of the original program.

Zgarb

Jul 9, 2021 23:01

@polcott But if H is just ignoring the checks performed by the simulated versions when it runs its own checks, it can erroneously claim that the simulated call H(x, x) will never return a value, even though (by your claim) it will return 0 and thus cause the simulated P(P) to halt. This breaks the "axiom" that H will only return 0 if the simulated computation actually never halts.

Zgarb

Jul 9, 2021 20:25

@polcott Okay, here's what I think I understand about your argument so far. Let me know if I'm wrong.

The function `H(F, x)` simulates the call `F(x)`, and periodically runs some basic checks to see if it never halts. These include a check for entering an infinite sequence of nested simulations that can't be aborted. If the simulation halts, `H` returns `1`; if a check succeeds, it returns `0`.

It is now clear that if `H(F, x)` returns `0`, then `F(x)` never halts.

You're claiming that `P(P)` enters this kind of infinite nested simulation, and `H` recognizes it and returns `0`. More prec…

Zgarb

Jul 9, 2021 14:55

@polcott Sorry, I meant to say never halting, that was a typo.

Zgarb

Jul 9, 2021 14:46

@polcott But this is confusing. How does it meet the definition of halting, and where does the axiom come in? Does H do a pure simulation?

Zgarb

Jul 9, 2021 14:45

@polcott I assume that a "pure simulation" is one in which the computation P(P) is just simulated step by step, with no interference, until it halts. If so, yes, this axiom is clearly true.

Zgarb

Jul 9, 2021 05:33

@polcott I agree with this. But if we call P((u32)P) in the main function, there is no halt decider watching its execution, right? It's just executed as it is, and we are interested in whether it finishes or not.

Zgarb

Jul 8, 2021 21:41

@polcott But isn't "prevention of infinite execution" just halting? A function call halts if it finishes execution.

Zgarb

Jul 8, 2021 20:23

@polcott So P((u32)P) halts. But if that's the case, shouldn't H((u32)P, (u32)P) then return 1, if H is to correctly decide this particular input?

Ilkka Törmä

Jul 8, 2021 19:13

@polcott Ok. Is one of them aborted?

Ilkka Törmä

Jul 8, 2021 19:13

Ok, that clears up the role of H. Now, what would be the result of running P((u32)P) in the main function? Would that computation halt?

Ilkka Törmä

Jul 8, 2021 19:13

Ilkka Törmä

Jul 8, 2021 19:13

Ilkka Törmä

Jul 8, 2021 19:13

Ilkka Törmä

Jul 8, 2021 19:13

I'm not familiar with C. What is (u32)P?

$Mathematics$ Discussion on answer by Lawnmower Man…

Imported from a comment discussion on math.stackexchange.com/q...

Zgarb

Jun 17, 2021 13:02

Why is your argument not contradictory with the one-dimensional CA in my answer? You don't seem to be using anything specific to Life, two dimensions, or a binary state set, so it should apply to my CA as well, but that one does have a black hole.

$Mathematics$ Discussion on answer by Yakk: Is blac…

Imported from a comment discussion on math.stackexchange.com/q...

Zgarb

Jun 17, 2021 13:01

This argument is still incorrect; see my answer.

Husk

A functional golfing language inspired by Haskell. GitHub: git...

Zgarb

Oct 29, 2020 13:04

Not sure if optimal

Zgarb

Oct 29, 2020 13:04

Try it online!

Zgarb

Oct 29, 2020 13:04

Hmm, might be easier to build the padding by hand and join

Zgarb

Oct 29, 2020 11:14

What do you mean by center? Pad with 0s?

Zgarb

Oct 29, 2020 10:25

I'm not sure if the behavior of r and i is fully documented. I should write that somewhere.

Zgarb

Oct 29, 2020 10:24

Yeah, that's probably what happens

Zgarb

Oct 29, 2020 10:14

So "2,3" -> "'2'\n','\n'3'" -> bunch of 0s with 2 and 3

Zgarb

Oct 29, 2020 10:12

Then mi gets the int corresponding to each char of the resulting string

Zgarb

Oct 29, 2020 10:11

¶ gets a string, which is a list of characters, and separates the elements by newlines

Zgarb

Oct 29, 2020 10:09

Ok I see what's up

Zgarb

Oct 29, 2020 10:07

Try it online! Ok there's definitely something fishy here.

Zgarb

Oct 29, 2020 10:05

@Razetime Hmm, I thought r was the problem, but changing it to i fixes it only partially: Try it online!

Zgarb

Oct 28, 2020 13:17

Jul 13 '17 at 10:06, by Zgarb

@MartinEnder It seems mathematically cleaner to me, if you think what happens when you remove the first "digit" in the base b representation of n. In the scheme where negative numbers have all digits negative, this means you get rem n (b^k) for some k (in Haskell syntax), and in the scheme where the first digit is negative, you get mod n (b^k). And mod is nicer than rem.

Zgarb

Oct 28, 2020 13:16

@DominicvanEssen That's by design

Zgarb

Oct 28, 2020 13:14

@LegionMammal978 No worries! I've been busy with real life stuff (and still am). Your latest patch looks good. You can do a pull request, maybe Leo gets notified.

Zgarb

Oct 21, 2020 20:07

I've been busy since Zgarb Jr's sleep schedule is evolving and he's tired and cranky...

Zgarb

Oct 21, 2020 20:06

And neither are binomial coefficients, which you maybe asked about earlier.

Zgarb

Oct 21, 2020 20:01

@Razetime No, and trigonometric functions aren't implemented either.

Zgarb

Oct 18, 2020 04:46

@LegionMammal978 It just picks the first one.

Zgarb

Oct 18, 2020 04:46

@LegionMammal978 That seems pretty short.

Zgarb

Oct 17, 2020 19:02

That might also not be optimal.

Zgarb

Oct 17, 2020 18:58

I can't think of a good general way of applying a function to a specific index or list of indices off the top of my head...

Zgarb

Oct 17, 2020 18:56

@LegionMammal978 Like this? Try it online!

Zgarb

Oct 17, 2020 18:41

@LegionMammal978 Honestly, because I didn't think of that when I wrote the parser. :P