The Nineteenth Byte

Anonymous

12:00 AM

Glad to help :)

New Main Posts

1:05 AM

0

Q: Test the endianness

Given a UTF-16 string, test its endianness. Rules: As long as the input is in UTF-16 without BOM, its type doesn't matter. In C++ on Windows, it can be std::wstring or std::u16string. In Haskell, it can be [Int16] or [Word16]. The endianness is tested by noncharacters. If the input contains a ...

PhiNotPi

2:32 AM

What is the most complex language for which you can compute the exact time complexity for any program/algorithm in the language?

LOOP (programming language)

LOOP is a programming language designed by Uwe Schöning, along with GOTO and WHILE. The only operations supported in the language are assignment, addition and looping. The key property of the LOOP language is that the functions it can compute are exactly the primitive recursive functions. == Features == Each primitive recursive function is LOOP-computable and vice versa.In contrast to GOTO programs and WHILE programs, LOOP programs always terminate. Therefore, the set of functions computable by LOOP-programs is a proper subset of computable functions (and thus a subset of the computable by WHILE...

Sriotchilism O'Zaic

@PhiNotPi I suspect that one does not exist.

PhiNotPi

There's this but it's actually too advanced. You can put an upper bound on time complexity though.

El'endia Starman

"What is the most complex language" oh boy, probably gonna be something suuuper complex "can compute the exact time complexity for any program" oh, probably something super simple.

PhiNotPi

I suspect it might be possible in a version of LOOP with only addition but no subtraction.

The issue with subtraction is that it's possible with have one variable of magnitude O(something big) and another variable with magnitude O(same big thing) but still have the difference between the variables be O(small).

Sriotchilism O'Zaic

Is there a proof that we cannot find the time complexity of algorithms in LOOP?

Oh wait I see.

Oh wait no I do not see.

Ok I think I have a proof that no such language exists.

PhiNotPi

2:40 AM

people.csail.mit.edu/meyer/meyer-ritchie.pdf

El'endia Starman

@SriotchilismO'Zaic Define "language" (maybe that's a question for @PhiNotPi).

PhiNotPi

Here's a paper where they talk some about forming an upper bound but that "The complexity problem for Ln is: given a program P in Ln determine whether Tp is bounded by f,_l (k) for any integer k. Theorem 6. For each n > 3, the complexity problem for Ln is effectively undecidable. "

Sriotchilism O'Zaic

Sorry I mean model not language.

PhiNotPi

The LOOP language can compute exactly the primitive recursive functions. (According to PPCG's slightly arbitrary rules, anything less powerful isn't considered much of a language at all.)

Sriotchilism O'Zaic

Oh my proof does not work.

Wait hold up, how are we defining time complexity over an abstract model?

What is to stop a model from "running in constant time" over every function?

El'endia Starman

2:47 AM

@SriotchilismO'Zaic That's an oracle machine.

Sriotchilism O'Zaic

Yes and what is to prevent that machine?

El'endia Starman

Simply say that the language must be executable by a Turing Machine. :)

Sriotchilism O'Zaic

Ok what is to prevent a oracle machine that only computes computable functions?

El'endia Starman

...that's just a Turing Machine?

Sriotchilism O'Zaic

No the Oracle machine takes constant time to compute every function while the Turing machine does not.

PhiNotPi

2:52 AM

Well with the LOOP language, it's essentially a question of how does the count of basic operations (starting a loop iteration, an addition, or an assignment) scale as the input numbers to the program scale.

El'endia Starman

In any case, I think it suffices to require the language to be executable by a TM. Oracles can do them in constant time, yes, but that's not "executable by a TM".

Sriotchilism O'Zaic

@El'endiaStarman I'm not sure what you mean by this?

@PhiNotPi This certainly makes sense, but once we get to more abstract edge cases, for example making each computable function a basic operation, I feel like we need a concrete definition.

PhiNotPi

And since you don't care about multiplicative factors when determining time complexity, figuring out the time complexity boils down to... if I double some of the input variables, how many more times do the bodies of the innermost loops have to be run?

Sriotchilism O'Zaic

Should we maybe define time complexity in terms of the complexity of an equivalent Turing machine?

El'endia Starman

@SriotchilismO'Zaic Phi's question was "what is the most complex language with computable time complexity for all programs?" and it's easy to require that such a language must be possible to implement with a Turing machine. An Oracle explicitly can do more than a Turing machine, and so are disallowed. Even if you restrict what the Oracle can compute, it's still not implementable with a TM because the TM does not have a magical oracle to ask.

PhiNotPi

2:58 AM

I don't know if we need to get this abstract? Unless we want to talk about computers that operate wildly differently than everyday computers, which I wasn't planning to get into. Because I think time complexity seems well-enough defined by saying addition/assignments are the basic unit operations.

Sriotchilism O'Zaic

Well if we do say time complexity is in terms of the equivalent Turing machine then there is no most complex model and my proof does work.

I think that we can show that the addition, subtraction, assignment definition of complexity is equivalent to the Turing machine definition.

The proof goes like this: Let us say that we have a model M which is the most complex model that can compute its own complexity. Let us take the set of functions computable by a Turing machine but not M (this must not be empty since it is weaker than a TM) and choose an arbitrary function from the list, f. Let us then make a new model M' which is identical to M except that it is augmented with a new atom which computes f.

This new model is more complex, since M could not compute f, but can still compute its own complexity, since the complexity of f is computable.

This is a contradiction since we started by saying M was the most powerful model that could compute its own time complexity and M' is more powerful, thus no most powerful language can exist.

El'endia Starman

I think "a new atom which computes f" is what hides all the extra complexity.

Sriotchilism O'Zaic

What do you mean by that?

El'endia Starman

That's simply not a thing you can do with a Turing machine.

Sriotchilism O'Zaic

Yes it is?

It does not need to compute f in constant time.

It just needs to compute f.

El'endia Starman

3:11 AM

No, it isn't. Turing machine: read symbol, write symbol, move head left, move head right, change state, and halt.

Sriotchilism O'Zaic

f is explicity a Turing computable function ?

El'endia Starman

Ah-ha, there's the extra complexity.

Sriotchilism O'Zaic

I'm not sure what is meant by "extra complexity"?

El'endia Starman

If you pick a function outside a given complexity class and include it as an "atom", then all programs are now in that complexity class.

Err, rather, the language is.

Sriotchilism O'Zaic

Yes, that is why M' is more powerful than M.

El'endia Starman

3:13 AM

So you can't say "pick an arbitrary function f" and claim that the language didn't get any more complex.

Sriotchilism O'Zaic

The language did get more complex, that is the point.

El'endia Starman

Okay, different tack.

9 mins ago, by Sriotchilism O'Zaic

This new model is more complex, since M could not compute f, but can still compute its own complexity, since the complexity of f is computable.

The complexity of addition, assignment, and looping are all computable and simple, but their combination in the LOOP language is not necessarily so.

Sriotchilism O'Zaic

Ah I see

I need to explain what is meant by adding atom

Let us say that M is defined by grammar where S is the start symbol.

El'endia Starman

Go on ahead. :) Meanwhile, my wife is pressuring me to head to bed, so I'll say g'night now and read your messages in the morning. :)

Sriotchilism O'Zaic

goodnight!

The grammar for M' is S' := S; S' := A; <the grammar of M> where A is the new symbol for f and S' is a new start symbol.

This adds exactly one new program, that computes f.

f cannot be used in tandem with previous programmes

Feel free to ping me if you are reading this tommorrow and you are having a question or issue with my proof. This is interesting stuff.

New Main Posts

6:11 AM

0

Q: Print the sequence

21, 21, 23, 20, 5, 25, 31, 24, ? Inspired by this Puzzle, given an integer \$n>0\$ , print out the following sequence until you reach a non-Integer (spoilered, in case you want to solve the puzzle yourself first) TestCases: Input and Output may be taken in any reasonable format, standard l...

code-golf

Cows quack

8:09 AM

rule30prize.org

5

Anush

8:52 AM

hi all

ngn

@Anush hi one

Anush

:)

I am thinking of a new coding challenge.. fastest-code I think

flawr

9:07 AM

in Primes and Squares, 46 secs ago, by flawr

Does anyone here know a simple GUI library for python? I want to do something that allows you to display images and draw on them - but I'm not familiar with building GUIs in python. I also considered doing the GUI in HTML/JS but again I have no experience with building a python webserver:)

ngn

9:21 AM

@flawr gimp not good enough?

flawr

@ngn Isn't that really complicated to access wtih python?

ngn

@flawr it has an api, idk much about it, i think it's in the other direction - gimp calls your py code

search for "python-fu"

flawr

9:44 AM

well gimp is probably way to powerfull for what I need

I maybe should have specified: I really only need to draw one color (black/white) with the mouse, maybe adjust the radius of the "brush" or something like that, which wouldn't be too difficult to implement anyway

Anush

10:20 AM

I was thinking of posing a fastest-code challenge around oeis.org/A161169 . But to make it more interesting I am dividing by the max possible and the code only has to output correct to three decimals places. Like this bpaste.net/show/Ygsg

it is worth trying with larger values of n

John Dvorak

Would a Monte Carlo algorithm be valid for that challenge?

Anush

@JohnDvorak sure! It just has to output the right answers up to 3 decimal places

I am wondering two things

a) what the output should be? I mean outputting all the values for k in range(int(n*(n-1)/2+1)) is quite a lot and b) if I should just give a score being the speed relative to the python code to make it easier for people to judge for themselves

any thoughts?

Anush

10:40 AM

how do I find the sandbox?

@flawr PyQt ?

@flawr or pygame?

Sherlock9

I've not completely read through all the mess of the past week because I've been dealing with my own troubles closer to home (look up Indonesia parliament protests) and at time of writing I'm at work, but I want to thank Dennis deeply for his years of service, first and foremost, and thank the other mods for theirs and their continued support despite this shitstorm.

Second and thirdmost, the Discord server is open, if a bit dead, and the CGCC gaming Discord server is also open and less dead.

Fourthmost, I haven't seen all the discussion around Axtell and its hiatus but if there's any way I can help with development now that I have a more stable situation post-university, I'd love to help. I know we have unresolved issues with what this sort of community migration/reboot/backup would entail, but frankly now seems like a good time to start hashing out those issues and continuing to develop a "backup" plan

ngn

11:19 AM

which reminds me, has anyone ever tried to back up tnb's chat log?

flawr

@ngn I'm not sure whether it uses a backup but @El'endiaStarman made the The Nineteeth Byte Data Explorer

@Anush go to codegolf.SE and click the link in the top right yellow box

ngn

@flawr looks like it works with real-time data

Anush

@flawr thanks. Good gave it to me in the end

flawr

@Anush have yo used any of those?

Anush

@flawr sadly no, sorry

New Sandboxed Posts

11:37 AM

0

A: Sandbox for Proposed Challenges

Compute A161169, approximately and quickly Input: Two values n and k. Output: T(n,k)/n! rounded to three decimal places. T(n,k) is defined by OEIS sequence A161169. questions For fastest-code, what should the input and output be?

Anush

12:38 PM

hi @Adám

Transcript for