The Nineteenth Byte

ais523

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

Someone

oh

ais523

@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

Someone

which one is that solving?

ais523

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

Someone

so how does the thing linked work?

and is the input fed to input pieces every tick? how does the input thing work?

ais523

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

Someone

@ais523 is this related to the Tower of Hanoi in any way?

ais523

@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

Someone

fair point.

ais523

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

Someone

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?

ais523

12:26 AM

that should be theoretically possible, but I doubt it's the simplest solution

Someone

it is a solution, though

if it's not completely stupid, anyway

ais523

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)

Someone

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

ais523

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

thejonymyster

~~oh god is this fancy L again~~

Someone

12:29 AM

@thejonymyster what's fancy L?

Yes, but hardcoding it in a language like Trianguish would waste space

thejonymyster

well we're going for infinite space so hardcoding a finite input isnt so much space wasted :P

ais523

you aren't wasting space because you don't have to copy the hardcoded input

Someone

and since space is the main limiting factor here, a viable program may require the presence of input to reduce space consumption

ais523

there is a trick: you can get each copy to provide input to the next one

Someone

but the space needed to create that number is important, right?

ais523

12:31 AM

like, you can leave a connecting wire and send "input" along the wire

Someone

like, an input of 23 would need only two cells max, but calculating 23 takes some space

and again, it's based on memory

thejonymyster

@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

class/family/whatever

ais523

@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

Someone

@ais523 what would that look like?

ais523

look at the link I posted above, it has a hardcoded 41 and 198 using this method

it takes up very little space

Someone

12:34 AM

it loops between the two values, I think

ais523

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

Someone

what would 23 look like? (also, how do you get a constant to output 1?)

what's the keybind for that?

ais523

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

Someone

how do s-builders work?

ais523

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

Someone

12:39 AM

oh, so they give output based on the number.

how do you give a non-NIL value for one tick?

ais523

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

Someone

clean!

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.

ais523

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

Someone

that's cleaner

and also eliminates the "making numbers is inefficient" problem

ais523

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)

Someone

12:55 AM

nice

ais523

err, O(n) time and O(1) memory, the memory is more important here

Someone

well, constant memory is useful

OldSandboxPosts

Sandbox posts last active a week ago: Tamagochi, Roll a ball down an array

Someone

what is that for?

Seggan

1:23 AM

@Someone if its a barebones TC language, it would have been Subleq

Someone

subleq is kinda weird

thejonymyster

@Seggan ehh there are many roads to rome

The Empty String Photographer

7:09 AM

Bar—Wi-Fi—Battery!

(full bars, Wi-Fi bars and battery!)

Dannyu NDos

10:16 AM

Where exactly is our policy stating that an integer may be I/Oed as a string of digits?

New Posts

10:43 AM

0

Q: What are our policies about this exotic I/O format about integers?

Please 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...

Dannyu NDos

Help

lyxal

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

also

62

A: Loopholes that are forbidden by default

Abusing 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...

New Posts

0

Q: Reconstruct an array by successive insertions

Given 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'...

code-golf

Simd

easy challenge posted!

lyxal

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

Neil

12:56 PM

@lyxal 4.5 is my favourite

lyxal

1:07 PM

Can't believe they found a way to make code golfing profitable and edible

Seggan

1:57 PM

@thejonymyster but only one Appian Way

Ginger

3:19 PM

The OSIRIS-REx mission's sample capsule has landed

Bbrk24

@Ginger I am not creating an account to read that

Ginger

eh, you can probably find it on NASA's website

Simd

4:16 PM

CMQ:is codegolf.stackexchange.com/questions/265455/… solvable in linear time?

The Empty String Photographer

4:41 PM

I'm not suspended on meta anymore!

I've served my hard time

And now for my feature request:

0

Q: Add collectives to other sites

On 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...

feature-request collectives

Neil

@Simd yes, but it's awkward in high level languages; would be a good fit for C though

Simd

5:08 PM

@Neil that would be cool

Sandbox Posts

8:19 PM

0

A: Sandbox for Proposed Challenges

Given 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 ...

Sandbox Posts

11:14 PM

0

A: Sandbox for Proposed Challenges

Barbrack 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. ...

Someone

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

Transcript for