The Third Stack

« first day (632 days earlier) ← previous day next day → last day (610 days later) »

user56656

02:58

@DestructibleLemon Try it online!

That is a program that removes the last bit from the current TOS and adds it to the end of the other TOS

(program in the comment)

We can use this to create a binary tape.

It is not a proof of TC, but it is a step towards one

Destructible Lemon

@user56656 nice

the only thing is using loops and stuff

because they check TOS

user56656

This flips the last bit on the current TOS

Destructible Lemon

i didn't even know brainflak had #-comments

user56656

It is implementation specific

Destructible Lemon

the only thing is that you can't rely on the second TOS...

i have an idea...

user56656

03:07

What do you mean by "you can't rely on the second TOS"?

Destructible Lemon

because of conditionals relying on at least one of the TOS

so you can't use it as a conditional like boolf***

but i have an idea...

user202729

@DestructibleLemon Huh?

user56656

Oh yes that is the issue right now.

user202729

You can calculate (n mod 2) and put it on the other stack to use as conditional.

Destructible Lemon

conditionals read the TOS, which means that, if you have any 1s on one side of the tape, will loop

user56656

03:08

It is hard to do conditional branching

Destructible Lemon

@user202729 but then you lose what was on that stack

user56656

@DestructibleLemon Not necessarily

There are more subtle limitations

user202729

@DestructibleLemon Use one stack for the tape, the other for conditional.

@user56656 Huh? What limitations?

user56656

Using one stack for the tape is a very hard thing to do

Destructible Lemon

@user202729 but the tape needs both stacks

user202729

03:09

But it's possible to extract any bit anyway, not just the last bit.

Destructible Lemon

my idea: use the difference in stack heights as a tape pointer

ASCII-only

@user202729 example program pls

user56656

@user202729 You can momentarily store the value from the second stack in the scope, but scopes have a strict order so you can only do your manipulations from inside the scope.

Destructible Lemon

you can move all of the tape to one stack, then do the conditional

user56656

yes but you need to store where you were, and you can't do that in scope memory

Destructible Lemon

03:11

yes, i said

user56656

because a loop can't cross a scope boundary.

Destructible Lemon

use the stack heights to store it

user56656

All of my manips wreak havoc on the stack height

Destructible Lemon

then move it back immediately afterwards.

user202729

@ASCII-only Let's see...

Destructible Lemon

03:11

@user56656 ah, but you can easily make them keep the stacks the same height

everytime you push to one stack, push a peek to the other stack

user202729

So, assume a program X evaluates to ToS mod 2 while does not change the ToS (is it possible?)

Destructible Lemon

use the height difference as the value

user56656

Maybe

Could work

I don't think we need to though

Destructible Lemon

@user202729 yes... in a way

user56656

@user202729 I can write that

user202729

03:14

Let's see... if it's possible to construct a snippet of programs that push the n'th bit on the other stack while leaving the current stack unchanged, it's TC, right?

Destructible Lemon

that's not how TC proofs work

that's a heuristic

user56656

I don't know but that is really easy to do

Destructible Lemon

if you can show that the ability to do that would allow you to compile a TC lang to this lang we are examining, then it would show it is TC

user202729

Then... you have infinite memory + conditional + loop. Why not?

About compile... yes, that need some work, but should not be hard.

user56656

It is not that simple.

Destructible Lemon

03:17

@user202729 probably, but you need to actually make a proof with the proper maths

y'know, show your working out and stuff

user202729

@user56656 How?

user56656

The problem is that you only have half a tape.

I.e. a stack of bits

user202729

... looks like I really need to make a compiler.

Destructible Lemon

you could make a tape with a single integer on one stack?

feersum

Compilers are a lot easier than math.

user56656

03:18

@DestructibleLemon Theoretically, yes, but it is hard in practice

Destructible Lemon

a compiler is maths, in a way

3 mins ago, by user56656

I don't know but that is really easy to do

user202729

Basic idea: if (bit[n]) {code} -> push bit[n] on other stack; <>; {<> code (<>)} <>

user56656

You have to shift all the even bits up and the odd bits down or something to that measure.

@DestructibleLemon That was about reading an arbitrary depth bit.

Destructible Lemon

@user56656 ok, but how does that not make it extensible to a tape?

user56656

How does that make it extensible to a tape?

user202729

03:20

After some more thoughts, it will allow the program to only be able to solve every problem with finite but arbitrarily large memory.

user56656

I'm not saying its not true, I just don't know why it would be true

@DestructibleLemon I should specify that I mean we can read an arbitrary bit that is determined at compile time.

user202729

Looks like that I overlooked something.
I think I will try the "shift all the odds bit up and all the even bit down" part.

Destructible Lemon

@user56656 oh ok

ok so, my idea is that you can just shift the bits onto the second stack, the one used for conditionals, when you want to check the bits and stuff, but then put them back, and set the stack height difference to be the bits to the left that the pointer is

user56656

I'm going to say that I believe this is TC, especially if we allow ourselves to use the stack heights

user202729

At least, with the ability to allocate memory fixed at compile time, it can solve a lot of problems now...

user56656

03:26

I think I know how we can do the one stack tape shifter

Destructible Lemon

are you using the stack height?

that could be helpful

user56656

I want to prove it TC without using Stack height

Destructible Lemon

why?

oh i guess there are valid reasons to do that

user56656

If we prove it TC using stack height that will just bring up the question of "Do we need stack height?" and then I'll be back to square one.

user202729

Smaller = better, right? That's why esoteric languages exist.

Destructible Lemon

03:28

@user56656 ok good point, but i mean, it might be easier to prove with stack height if we do happen to need stack height

user56656

Also I'm not certain we need <...>

Destructible Lemon

@user56656 we don't, but that's well known

user56656

We don't if we have a pop

Destructible Lemon

@user56656 wait, i take that back. yeah i just though of that

@user56656 use the second stack as a working variable, as we only really use that for loops?

user56656

Are you replying to the correct message?

Destructible Lemon

03:32

yes

user202729

... Single stack shifting is harder than I thought at first.

Destructible Lemon

i mean, if you push the thing you want to evaluate to onto the offstack, you can then peek it negatively

user56656

I'm not sure how we would get rid of <...> I just haev a suspicion

Destructible Lemon

maybe we should discuss this in the third stack

user56656

Perhaps

Hm, how do I move messages.

user202729

03:34

@user56656 I don't think you can as you're not a TNB room owner / mod.

user56656

Ah I need to be a TNB owner.

that feels a bit backwards.

@DJMcMayhem I see you are in the room. Would you mind moving this convo?

Destructible Lemon

@user56656 you mean having to own the room where the messages originated?

it makes sense when you consider only some of the messages are yours

user56656

I am a RO of the Third stack but not TNB

Destructible Lemon

ok so who are you actually

user56656

I was WheatWizard

Destructible Lemon

03:41

oh ok

madness

Dennis

@user56656 Where does it start and where should I move it to?

user56656

@Dennis Starts here could you move it here? Thank you.

It is an entirely contiguous chunk too so no need to worry about other messages getting caught

Dennis

← 119 messages moved from The Nineteenth Byte

user56656

tio.run/##VY1BCsQwCEX3PUVgNrroDcSLlCxShsLQ0kW3krPbfCedMIh8/…

I just realized what time it is. That is a WIP and I will try to finish it tomorrow.

I think the single stack tape is probably possible though.

« first day (632 days earlier) ← previous day next day → last day (610 days later) »

all rooms

Transcript for

Mar11

Mar '1819

Mar20

A chat room for discussing the Brain-Flak programming language...

brain-flak confusing-languages scary-pencils what-does-my-code-do?

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC