The Nineteenth Byte

Steven H.

10:00 PM

@ConorO'Brien ^^^ if you're dealing with arbitrary-size integers as opposed to constant

Conor O'Brien

oh interesting

ATaco

(Alternatively you could assign memory just for the size of an int :P)

Conor O'Brien

@MarcusAndrews eval gets.tr" ","*"

quartata

@ConorO'Brien that's a good idea

Conor O'Brien

thank you

ATaco

10:05 PM

function reverseNumber(a){
	var b = 0;
	while(a > 0){
		b *= 10;
		b += a % 10;
		a //= 10;
	}
	b;
}

Try it online!

quartata

?

Conor O'Brien

@Adám I have no idea, I don't apl very well

ATaco

That's constant memory (As Funky only uses Doubles)

Steven H.

@ATaco chat.stackexchange.com/transcript/message/41391573#41391573

ATaco

'eh.

quartata

10:07 PM

@ATaco you need to hoist the temporaries out of the loop

otherwise they'll linger until GC and make it logarithmic memory

assuming you aren't doing escape analysis that is

ATaco

dowatnow?

Adám

@ConorO'Brien It inserts the function {⍞←⍺} between the digits. So you get '3'{⍞←⍺}'1'{⍞←⍺}'4'{⍞←⍺}'1'{⍞←⍺}'5'{⍞←⍺}'9'{⍞←⍺}0. APL evaluates from right to left, each function outputting (and returning) its left argument.

ATaco

This is above my pay grade.

Conor O'Brien

@Adám I think that's non-constant memory, since it sort of uses the program as a memory bank (which is more memory? I think? Idk)

ATaco

(I assure you those 10's are recognized as constants and are only stored in memory once)

caird coinheringaahing

10:09 PM

@FlipTack Why I hate online leaks. I just hope we don't have to do it again (and that we get our code back)

quartata

Yes, but b *= 10 -> b = b * 10, and b * 10 is probably stored in a temporary

ATaco

To my knowledge, based on how Funky works, this shouldn't use additional memory for each iteration.

Steven H.

@Adám no stringification, that's O(log_10(n))

Adám

@ConorO'Brien But each function never holds more than two digits.

@StevenH. It takes string input from STDIN.

ATaco

b*10 is stored temporariliy, and I'm not sure how that much is handled.

That's NodeJS's problem though.

Adám

10:11 PM

@ConorO'Brien Wait, do you mean O(1) as opposed to O(n) or O(n) as opposed to O(2×n)?

Conor O'Brien

@quartata aren't compound operations like that optimized? esp. by a constant

@Adám I mean O(1) basically

quartata

@ConorO'Brien This is Funky though

ATaco

@Adám Regarding that issue on the Taco's Userscripts GH, I'm not sure how many people prefer the Colon after the Bytes for CMCs.

Conor O'Brien

function reverseNumber(a){
    var b = 0;
    var c;
    while(a > 0){
        b = b * 10;
        c = a % 10;
        b = b + c;
        a = a// 10;
    }
    b;
}

Adám

@ConorO'Brien I don't think that is possible, as each digit takes constant memory, and you need to hold them all before beginning output.

quartata

10:13 PM

@ConorO'Brien yeah, this is what I meant

Conor O'Brien

@Adám well, it has been demonstrated here it is possible

ATaco

@ConorO'Brien I assure you due to how funky works that isn't more efficient.

Conor O'Brien

6 mins ago, by Steven H.

@ATaco https://chat.stackexchange.com/transcript/message/41391573#41391573

Adám

@ConorO'Brien Doesn't 123456789 take more memory than 12?

Potato44

I think @ConorO'Brien means O(1) excluding the input

Conor O'Brien

10:13 PM

yeah

Steven H.

^^

Conor O'Brien

since it's a number, and I'm disregarding number width

quartata

although tbf both fit in a 32 bit integer

ATaco

And the *=, += and //= are syntatically equivalent to their a = a + counterparts.

Adám

@ConorO'Brien Well, then I think my code works too. It takes the number in as a string, then processes only two digits at any given time.

Marcus Andrews

10:14 PM

Hm or a shorter way to read in a sorted string in ruby other than gets.split("").sort ?

quartata

oh actually I didn't mean b = b * 10; though

Conor O'Brien

@MarcusAndrews gets.chars.sort, perhaps?

quartata

need another temp outside of the loop for b * 10 most likely

Steven H.

With constant number width chat.stackexchange.com/transcript/message/41391573#41391573 works, and with arbitrary number width chat.stackexchange.com/transcript/message/41392071#41392071 works

Adám

@ATaco Hm, ok.

Marcus Andrews

10:15 PM

ah perfect!

thanks Conor

Conor O'Brien

np

ATaco

So although it's intended to not have a colon, if it's preferred to be with one it's an easy change.

quartata

@ATaco When you do b += a % 10;, there's a temporary being created for the a % 10. This is recreated each iteration

assuming no optimization is done and they're all on the heap

Hence "hoist out of the loop"

Steven H.

@Adám Does it store the other elements on the callstack then?

Conor O'Brien

@Adám but does it store all of the digits in memory, no? the program state should still consist of those values, which is O(n) memory afaict

^^

ATaco

10:16 PM

Storing the value in c in Funky isn't any more efficient, as Funky makes no effort to optimize the memory.

quartata

This isn't about runtime

This is about memory

c is only made once

Conor O'Brien

it could have O(n!!) runtime but all it needs is O(1) memory

Adám

@StevenH. It has to keep the digits in memory, but then it chops one at a time from the end, until none are left.

ATaco

What I'm saying is that funky doesn't care that you're assigning to c.

quartata

@ConorO'Brien although most of these are going to be O(log n)

Steven H.

10:18 PM

The callstack looks like it'll be of depth O(n) though

Adám

@StevenH. I don't understand what you mean by callstack.

Conor O'Brien

@quartata but Steven's should be O(1), disregarding the input width?

quartata

@ConorO'Brien I mean runtime

Conor O'Brien

oh ok

quartata

@StevenH. pretty sure it's tail recursive

ATaco

10:19 PM

Even though it ideally would store the variable only in the memory c holds, Funky does not use this, and storing it in c simply duplicates it from the value of this expression, much like evaluating b += would.

Steven H.

Tail recursion would make sense

quartata

@ATaco So you're saying it makes a temporary and then copies it into c?

Adám

@ConorO'Brien program state?

quartata

In that case it's impossible to make it constant memory

ATaco

Correct. And sad.

Conor O'Brien

10:20 PM

@Adám the layout of all the memory the program has allocated to it, iirc

quartata

@StevenH. I can't really read the APL but it looks that way

I'm sure Dyalog APL does TCO

Adám

@quartata It does. Tail recursion is free forever.

Steven H.

I just read '3'{⍞←⍺}'1'{⍞←⍺}'4'{⍞←⍺}'1'{⍞←⍺}'5'{⍞←⍺}'9'{⍞←⍺}0 as ((((('3'){⍞←⍺}'1'){⍞←⍺}'4'){⍞←⍺}'1'){⍞←⍺}'5)'{⍞←⍺}'9'){⍞←⍺}0

quartata

@Adám then you're good, it's O(1)

because the previous stack frame is gone

Conor O'Brien

kudos for probably having the shortest O(1) solution, I'm shocked :D

quartata

10:22 PM

although if it takes string input then you could just reverse it in place

Adám

@quartata Yup, and that has been super-optimised. But where's the fun in that?

Conor O'Brien

true, but that goes against the spirit of "constant memory" :P

and against numbers

Adám

@quartata As of the current version, we even do matrix transposes in place.

ATaco

Most importantly, these solutions only work on numbers of constant size.

If you assume arbitrary ints, than memory becomes arbitrary as well.

Conor O'Brien

that's why I said "of unspecified size", so it remains general to arbitrary ints, but without arbitrary memory

Marcus Andrews

10:25 PM

Hm is there a shorter way in bash to do a reverse range?

e.g. if I am doing tr 01234 98765 I can do tr 0-4 98765 but it doesn't like tr 0-4 9-5 because the 9-5 is in reverse order

Conor O'Brien

seq 4 9|tac

e.g.

Marcus Andrews

does that work with my tr code?

Conor O'Brien

oh, nvm, misunderstood

yeah, nothing shorter than hardcoding it

Marcus Andrews

from what I can tell tr doesn't allow any reverse range workarounds without adding more chars anyway

Steven H.

I feel like taking in a *non-*integer is cheating... but if we're allowing string input, #pe~P

(Pyth, 5 bytes)

@ConorO'Brien Allowing only actual integer input is far more exciting

Conor O'Brien

10:31 PM

indeed it is!

quartata

What prompted this anyways

Conor O'Brien

1 hour ago, by Conor O'Brien

CMC: Reverse the digits of an integer with constant memory. (I have no idea if this is possible but I feel like it is)

Steven H.

And, as it turns out, it's possible

quartata

@ConorO'Brien yeah but like why

Conor O'Brien

1 hour ago, by Conor O'Brien

this would be helpful in many esoteric languages, all of which I see utilize linear memory for custom integer input, which becomes bothersome for further generalization for, say, brainfuck into higher level languages

quartata

10:41 PM

Oh, OK

Conor O'Brien

I've gone from implementing languages to implementing languages that compile to esolangs

quartata

I mean tbf assembly is the original esolang

compilers are fun

Conor O'Brien

^

Steven H.

CMC: Solve the halting problem for a version of (technically-not-turing-complete) BF with finite-size wrapping memory

The M stands for Mega, and it's a theoretical computation

Conor O'Brien

that's the original spec of BF

30,000 cells of 8-bit cells

Steven H.

10:45 PM

Huh

Regardless, the halting problem is solvable under that original spec

Conor O'Brien

yup

Steven H.

Not within our universe, of course, but it's solvable

ATaco

Assuming you're using a Turing complete language to do this; Just store every state that the BF program goes through, and if the BF program ever returns to this state, stop it and return non-halting. If it halts, well then it's halting.

Conor O'Brien

not necessarily

ATaco

There are some busy beavers, such as +[+>] which will take a ridiculous amount of time and memory, but assuming you're using a TC langauge, you will eventually solve it.

Conor O'Brien

10:52 PM

what about a program like -+- followed by some other stuff? You'll have encountered an already seen state, but no looping has occurred, and you will have concluded it does not halt

ATaco

the Instruction Pointer is part of the state.

quartata

Yep

Conor O'Brien

@ATaco I still don't see how the program cited does not produce wrong results

quartata

Pigeonhole principle but with arbitrarily large n basically

ATaco

Because at the second - it's not in the same state.

The IP has moved.

Conor O'Brien

10:57 PM

oh, ip, right

I misread as the tape pointer

ATaco

(But that's also important)

Conor O'Brien

yeah oc, but I disregarded the IP

Anonymous

Enumerating every state of a bf program isn't that unreasonable - 30 KiB for the tape, 15 bits for the tape pointer, and ceil(log2(n)) bits for the IP (where the program is n bytes long), per state.

Anonymous

And that's an upper bound - if you can prove that the IP has a maximum < 30k, you can shrink the memory requirement for the tape

DJMcMayhem

@Mego Only problem is that you could arbitrarily increase the program length

Although I guess it's growing logarithmically

Anonymous

11:03 PM

@DJMcMayhem Well sure, but I'm talking about the memory requirements per program

Anonymous

@DJMcMayhem It actually grows factorially (that's totally a word), because every new instruction adds more permutations of the state

Steven H.

So what about input

Anonymous

@StevenH. Just make it a closed system. Replace each , with the appropriate number of +s, and discard .s.

DJMcMayhem

@Mego So it's actually (30 KiB + 15b * n) + ceil(log2(n))?

Steven H.

Nope, that's not the challenge. Solving the halting problem requires input be taken into account

https://en.wikipedia.org/wiki/Halting_problem

> the halting problem is the problem of determining, from a description of an arbitrary computer program **and an input**, whether the program will finish running or continue to run forever.

ATaco

11:07 PM

Input should be [-]++++... for the more standard approch.

Anonymous

@StevenH. Yes, and the input is part of the program. You preprocess it to an equivalent program with hard-coded input.

Destructible Lemon

@StevenH. tbf it's basically the same problem with or without input really

ATaco

.And input refers to starting state.

Which in this case, in the program.

Destructible Lemon

ninja'd i guess

Steven H.

[.>+] can't be hardcoded

Anonymous

11:07 PM

@ATaco Yeah that

Anonymous

@DJMcMayhem Why are you multiplying the 15 bits for the TP by n? The number of bits needed for the TP isn't affected by the length of the input. I think it should be a +.

Conor O'Brien

the turing completeness of a language does not hinge on input; consider a subset of BF without IO. It is TC iff BF is TC, ergo input is spurious

Anonymous

@StevenH. Sure, but you can just consider the input for that. That program halts iff the input is finite.

Anonymous

And I'm assuming you meant , instead of .

ATaco

A Turing machine doesn't require input (As the Turing Tape Machine has no method for input)

Steven H.

11:09 PM

yeah, I did @Mego

Anonymous

Then input doesn't matter at all, because the input is never used

Anonymous

Oh I misread that message

Anonymous

Ignore my previous message

Anonymous

If input is finite, you can unroll the loop, and therefore it halts. If input is infinite, then the program doesn't halt.

Steven H.

Truth machine implementation?

Anonymous

11:13 PM

Of course, because the halting problem is concerned with TMs, which have hardcoded input, you can't have infinite input anyway, so the problem is moot.

Steven H.

,[[-]+.].

Anonymous

@StevenH. What about it?

Steven H.

Finite input, doesn't necessarily halt

Anonymous

But you're looking at whether the program + input combo halts

Anonymous

7 mins ago, by Steven H.

https://en.wikipedia.org/wiki/Halting_problem

> the halting problem is the problem of determining, from a description of an arbitrary computer program **and an input**, whether the program will finish running or continue to run forever.

ATaco

11:15 PM

Once again, Input is just the initial state of the program.

Anonymous

@ATaco Exactly. You can take a BF program and an input, transform that into an equivalent BF program that does no I/O, and then reason about that program wrt the halting problem.

Destructible Lemon

it seems like the input thing was just to help disprove the halting problem solvability or something

Steven H.

Even with infinite input there's only finitely many states so you can still reason about it

Anonymous

@StevenH. Well yes, but doing the transformation makes it much simpler to enumerate all of the states

Conor O'Brien

isn't it simple enough to reduc 30k-cell BF to a tape with a 1-bit cell and claim they have the same computational class because they both have finite memories?

Steven H.

11:21 PM

How do you transform infinite input, though?

Anonymous

@StevenH. Are you serious? I just explained that.

Destructible Lemon

@Mego input in loops?

Christopher 2EZ 4RTZ

To the people who say cats>>dogs I say WRONG. cats>>1, (9

Steven H.

@DestructibleLemon THANK YOU.

Destructible Lemon

@Christopher2EZ4RTZ maybe not >>... cats>dogs though

Anonymous

11:24 PM

11 mins ago, by Mego

If input is finite, you can unroll the loop, and therefore it halts. If input is infinite, then the program doesn't halt.

Conor O'Brien

@Mego what about infinite input to the program ,.?

Steven H.

Input can be infinite and still not be entirely read

Anonymous

@ConorO'Brien That one halts regardless of the input.

Destructible Lemon

ok but wouldn't making the input when input is in loops be less trivial

Conor O'Brien

but your statement seems to imply infinite input necessitates a program that doesn't halt

Anonymous

11:25 PM

@StevenH. Sure, but you can prove that, and do the hardcoding input transformation

Steven H.

[,>+] halts on infinite input iff somewhere the input contains 255

how would you hardcode that

Anonymous

@ConorO'Brien No, it means that if a program has a loop whose ending condition is end of input, the program doesn't halt if the input is infinite.

Conor O'Brien

I see

Steven H.

(By 255 I mean 0xFF, of course)

ATaco

Infinite Input really seems out of scope of the problem.

Conor O'Brien

11:26 PM

^

Steven H.

It's solvable though /shrug

Anonymous

@StevenH. You drop everything except the \0xff byte in the input (if it exists), and transform it to x[] (where x is + if \0xff exists in the input, else nothing).

ATaco

Because, unless the program is very specifically talored, the only way to know if an infinite input (which may as well be random bytes) will halt or not is to determine if the infinite input contains the correct sequence to halt it. Which is predicting an impossible RnG.

Steven H.

How do you use that transformation to solve the halting problem? That's assuming knowledge of the answer already

Anonymous

@StevenH. Ok let me explain this as simply as I can

Steven H.

11:29 PM

@ATaco This is a theoretical computation, you can view the powerset

Conor O'Brien

@ATaco isn't that some theorem? given infinite time and a uniformly random RNG, it will eventually reproduce every subsequence?

ATaco

Uniformly random is incorrect for user input, and once again, this is trying to solve the halting problem, not guess when it might halt.

Anonymous

You have your program [,>+] and your input. If the input contains 0xff, then the program can be translated into the equivalent program [] (or even the empty program), which is trivial to prove that it halts. If it doesn't, then you can translate it to +[], which is trivial to prove that it doesn't halt.

Conor O'Brien

(sorry my question was significantly tangential)

Steven H.

How do you algorithmically create this transformation then?

Anonymous

11:32 PM

Actually, by the original definition of BF, [,>+] always halts, because the program halts if the IP goes off the edge of the tape.

Anonymous

@StevenH. I don't care to try to develop it right now, but it is possible, because it is possible to prove whether or not a BF program (using the original BF definition) halts with a given input.

Steven H.

The original question referred to wrapping memory

Anonymous

@StevenH. Wrapping memory means that the 8-bit memory cells wrap on over/underflow

Steven H.

That was unclear then, I meant the memory pointer wrapping

that's my bad

Anonymous

Even if the tape pointer wraps, it's still possible to prove whether or not a program halts with a given input, because it's still not TC

Steven H.

11:36 PM

i.e. <+[] doesn't halt because it wraps around to the 30,000th byte in memory

ATaco

+[<[-]+]

Steven H.

^^^ Yes, but I don't see how solving the transformation in a general case is easier than solving the halting problem in the first place

ATaco

+[>+] in a TC variant of Brainfuck will never share a previous state, so (alteast via this method) cannot be solved for halting.

Anonymous

@StevenH. I never said it was easier to come up with a transformation. I said it was easier to reason about a I/O-less version of BF, and that it is possible to transform any BF program into an equivalent program with input hardcoded that does no I/O.

ATaco

Throwing a complex Random Number Generator into the mix via the usage of Input just complicates things unnecessarily.

Anonymous

11:39 PM

With an I/O-less version of BF, the input is part of the program, so you only have to reason about the program itself, rather than both the input and the program.

Steven H.

@Mego this is the problem I think you come across if you try to solve the transformation for a general case

Anonymous

And this discussion is no longer productive or meaningful. Goodbye.

Steven H.

Bye, I guess

I just don't believe that solving the transformation from infinite input+BF program -> inputless BF program is an easier problem than solving the halting problem the naive way

Conor O'Brien

7 mins ago, by Mego

@StevenH. I never said it was easier to come up with a transformation. I said it was easier to reason about a I/O-less version of BF, and that it is possible to transform any BF program into an equivalent program with input hardcoded that does no I/O.

I don't believe he was arguing that it was easier. He was saying understanding was easier, and that the understanding is correct since there exists a translation.

Steven H.

I don't disagree with the understanding being easier, but it doesn't get any closer to a solution. Mego seemed to be trying to solve "prove that the halting problem is solvable for programs in this language" rather than "solve the halting program for programs in this language"

I guess I should have realized that before I chased him off.

@Mego I'm sorry, if you care to accept this apology

ATaco

11:52 PM

CMC: Given a number a, Determine if in base b all the digits are greater than c. Bonus points for a solution that doesn't rely on base conversion.

Neil

@ConorO'Brien Charcoal, 2 bytes: αβ

Conor O'Brien

how succinct!

ATaco

@ConorO'Brien RProgN 2, 3 bytes Aa.

If you're allowed a newline between the cases, you can alternatively do aA

Neil

@StevenH. Charcoal, 7 bytes: ✂γ³³¦⁹¹

Transcript for