« first day (4621 days earlier)      last day (238 days later) » 

12:01 AM
there's a language called P'' that predates BF
and is basically the same, but without the I/O commands
BF was discovered independently, I think, and was given I/O because it was designed as a minimal programming language rather than a minimal TC language
@RydwolfPrograms: I think there are two fundamental problems in proving Trianguish Turing-complete, but I solved one of them
unfortunately the details of this solution imply that the other one is probably quite difficult
which one is that solving?
there is a sequence of input that can path to an arbitrary point on the grid and place an arbitrary symbol there
i.e. a universal constructor exists
so how does the thing linked work?
and is the input fed to input pieces every tick? how does the input thing work?
12:13 AM
input is read every three ticks
the basic idea is to form a single path along which all communication is done
to build op X on cell Y, you first recursively build a builder on cell Y-1, then recursively build a wire on cells 0…Y-2, then use that wire to tell the builder to build on cell Y
and then you can recursively delete the cells again if you want to get rid of the wire
the relevant OEIS sequence is oeis.org/A014577
anyway, the basic problem is that this sort of constructor can only reach a distance equal to the number of bits of memory it has, making it hard for a program to construct something larger than itself
@ais523 is this related to the Tower of Hanoi in any way?
@Someone it is pretty similar, both this and the Tower of Hanoi are recursive problems that have recursive solutions, so the resulting patterns look much the same
but the details are different so the solution sequence ends up different
fair point.
anyway, I suspect this probably is TC because it's a two-dimensional language, so if a program can reach a distance proportional to the number of bits of memory it has, it can cover an area proportional to the square of the number of bits of memory it has
which means that a program can construct semething larger than itself, if you "fold" the memory along a space-filling path, and the program is sufficiently large
but it would be a lot of work to construct something like that, as you'd basically need to make a quine that has a shape more complicated than just a single line
could a program recursively build an object to increase the number of bits of memory, and then use that memory to make something even larger?
Or would such an exponential building pattern lead to a roadblock somewhere in that process?
12:26 AM
that should be theoretically possible, but I doubt it's the simplest solution
it is a solution, though
if it's not completely stupid, anyway
all you need for a solution is a program that's capable of copying itself – once you can do that, you can access all of memory
because you can move around to reach spots using O(log n) bits of memory rather than O(n)
would a program that depends on input to do so still be viable for a TC proof?
like, if it needs an input of [32, 64, 128] or something like that
it is possible to have a language which can write an interpreter for a TC language but is not TC itself, because it critically depends on the presence of input for some features of the language to work at all – it is a matter of opinion whether to consider those TC or not
but it's generally a pathological case, in most languages (including Trianguish), if it is possible to read something from input it is also possible to hardcode it
oh god is this fancy L again
12:29 AM
@thejonymyster what's fancy L?
Yes, but hardcoding it in a language like Trianguish would waste space
well we're going for infinite space so hardcoding a finite input isnt so much space wasted :P
you aren't wasting space because you don't have to copy the hardcoded input
and since space is the main limiting factor here, a viable program may require the presence of input to reduce space consumption
there is a trick: you can get each copy to provide input to the next one
but the space needed to create that number is important, right?
12:31 AM
like, you can leave a connecting wire and send "input" along the wire
like, an input of 23 would need only two cells max, but calculating 23 takes some space
and again, it's based on memory
@Someone ℒ, also known as "Fancy L" is a class of programming languages that can implement TC languages but do nothing else, and its a philosophical question as to whether these are TC or not / whatever. It's only tangentially relevant :P
@Someone hardly any, you just hardcode the op with value 23 as an instruction in your program and use an s-builder to read it directly out of the source code
@ais523 what would that look like?
look at the link I posted above, it has a hardcoded 41 and 198 using this method
it takes up very little space
12:34 AM
it loops between the two values, I think
e.g. the bottom-most two ops in the program provide a hardcoded 198
actually implementing the looping behaviour was harder than hardcoding the constants
what would 23 look like? (also, how do you get a constant to output 1?)
what's the keybind for that?
go to a blank cell and press E a few times until you find the constant-1 op
the constants are basically just an s-builder, with a nil build-input, and a particular op on its build-cell
because the build-input is nil they don't build anything, and as long as the number you want to hardcode is a valid op you just put that op on the build-cell – as nothing is reading its output, and it is surrounded by nils, it won't do anything regardless of what command it is
how do s-builders work?
they have a build-input, a build-cell, and an output: if the build-input is non-nil they change the op on the build-cell to the build-input; and the output is the numerical value of the op on the build-cell
12:39 AM
oh, so they give output based on the number.
how do you give a non-NIL value for one tick?
this is surprisingly difficult: the solution in my link sends a constant along a wire, but deletes the wire as the data starts to move along it, so only one tick's worth of data gets through
you only have to do that once, because once you have a signal that's "non-NIL for only one tick" you can use that to control other things to be non-NIL for only one tick
so you can just do it at progrma startup
I would ask if there was a way to have two wires bypass each other, but there are only 3 places per cell, so that never needs to happen.
anyway, I just realised that there's a more asymptotically efficient way to do the construction: you can just build the "building" part of the constructor elsewhere, whilst leaving the "thinking about what to build" part of the constructor in its original location and connecting by a wire
meaning that you don't necessarily have to build a copy of yourself – just something of constant size
this makes things much easier
that's cleaner
and also eliminates the "making numbers is inefficient" problem
because it implies that you can build an arbitrary repeating pattern in O(n) time, which is clearly enough for TCness
(building a self-replicating program is possible, but no longer necessary for the TC proof)
12:55 AM
err, O(n) time and O(1) memory, the memory is more important here
well, constant memory is useful
Sandbox posts last active a week ago: Tamagochi, Roll a ball down an array
what is that for?
1:23 AM
@Someone if its a barebones TC language, it would have been Subleq
subleq is kinda weird
@Seggan ehh there are many roads to rome
6 hours later…
7:09 AM
(full bars, Wi-Fi bars and battery!)
3 hours later…
10:16 AM
Where exactly is our policy stating that an integer may be I/Oed as a string of digits?
10:43 AM
Q: What are our policies about this exotic I/O format about integers?

Dannyu NDosPlease refer to this post on Sandbox. Basically, the proposed challenge is about a new numeral system I made. Though the proposal doesn't require the I/O format to be in the numeral system, I have a serious problem now: This opens new possibility for an I/O format about integers. AFAIK, our defau...

11:30 AM
simple solution, just restrict input to integers and post
afaik there's no languages right now that use that number system
and once you've posted, languages that would have a system that trivialised that number system would be considered unfunny
A: Loopholes that are forbidden by default

DennisAbusing native number types to trivialize a problem It is common practice to restrict challenges to cases where input, output and/or intermediate values of the algorithm of choice fit into the language's native number type. At least for input and output, this is generally assumed even if not sta...

Q: Reconstruct an array by successive insertions

SimdGiven an array of letters in the range 'a' to 'o', compute how to construct the array by successively inserting the letters in alphabetical order. You will always start the insertion with a base array of all the 'o's that are in the array to be reconstructed. Examples Let the input array be: ['o'...

easy challenge posted!
12:29 PM
TIL the HNQ list can link questions you're currently viewing leading to a potential for infinite recursion
aw only 3 recursions
12:56 PM
@lyxal 4.5 is my favourite
1:07 PM
Can't believe they found a way to make code golfing profitable and edible
1:57 PM
@thejonymyster but only one Appian Way
1 hour later…
@Ginger I am not creating an account to read that
eh, you can probably find it on NASA's website
4:16 PM
CMQ:is codegolf.stackexchange.com/questions/265455/… solvable in linear time?
4:41 PM
I'm not suspended on meta anymore!
I've served my hard time
And now for my feature request:
Q: Add collectives to other sites

The Empty String PhotographerOn Stack Overflow, there is something called collectives. Collectives are a way of organising information on different topics related to the site. However, I would like to see collectives on other sites. Here are some examples of how they could be used: A Linux collective on Super User Collectiv...

@Simd yes, but it's awkward in high level languages; would be a good fit for C though
5:08 PM
@Neil that would be cool
3 hours later…
8:19 PM
A: Sandbox for Proposed Challenges

thejonymysterGiven A Binary String, Determine Which Of Certain Substrings Are Equal And Opposite yea the title is going to need some work Concept Take an even length binary string 1 1 0 1 0 0 1 0 Between each digit, place an arrow 1 1 0 1 0 0 1 0 ^ ^ ^ ^ ^ ^ ^ These provide "centers", and then you (mumble ...

3 hours later…
11:14 PM
A: Sandbox for Proposed Challenges

SomeoneBarbrack Your task is to write a program or function that takes a non-negative integer (in decimal or any other convenient base for your language) and output a number in the numbering system Barbrack. What's that? Barbrack is a numbering system I made up that can represent non-negative integers. ...

11:53 PM
how come my answer with a custom numbering system is literally right next to another answer with a custom numbering system
I really hope it's not the same one xD
nvm it's not

« first day (4621 days earlier)      last day (238 days later) »