C(odemonkey) S(tudies) general

> tfw no CS general

Here's a cool problem: shew that it is impossible to decide the language of binary palindromes on a one-tape Turing machine in less than quadratic time.

...

long time since i've done one of these problems.

easy to see why it's true. the head has to go back and forth O(n^2) times to compare the elements.

should i use a reduction from some known quadratic problem? i forget how these proofs usually go.

I cant imagine how much anime is in the /g/ generals. It must be literally drowing in anime since theres so many brainlets

Answer the question then pussy if it's such brainlet tier.

I've never done this before, I've programmed like 3 TMs in my time in an advanced logic class on recursion theory (like 2 years ago). I don't know any computable reducibilities. So this may be completely wrong.

I'm not going to write out the specific instructions, but what the TM should do is use {b,1,0} for a language where a blank. Check the first number, if 1 write 0, move right until hits blank, now move left, if 0 halt. If 1 blank it, and move left until blank, move right and blank. This is already 2n+2 moves. Now move right and repeat the algorithm. Now the length of the word is n-2, it will take 2n steps to repeat the algorithm, and so on, so:

2(n+1+n+...+2+1)=n^2+n.

For the case the TM see's a 0 first do the same process but opposite writing keep the states separate so that the machine will always know what it wrote down.

I forgot to say the machine will halt because it's not defined for moving left and seeing a blank.

that's just an O(N^2) program. you have to prove that ANY program performing the task must have at least O(N^2) complexity.

God dammit, you're right.

* it uses O(N^2) single-cell moves. the number of times it goes back and forth is O(N)

OP should give an exact definition for his turing machine.

i don't remember enough to do this off the top of my head.

If you could do it in less than quadratic time, you could decide equality by communicating less than linearly many bits.

Consider simulating the TM on the string [math]x 0^|x| y^R[/math]

Person A has the string x and person B has the string y and they want to determine if x=y by sending as few bits as possible.

There is a position in the middle where the tape passes fewer than linearly many times.

Person A simulates the left part, Person B simulates the right part, and they send the state back and forth when it reaches the middle position.

So we decide equality with less than linear communication which is impossible

your latex is kind of fucked. could you fix it? i want to see the answer.

>There is a position in the middle where the tape passes fewer than linearly many times.

it looks like you're just asserting this rather than proving it.

similar to what I was thinking for my proof. if you can decide palindromes in less than quadratic time you can decide equality in less than quadratic time by reversing one of the strings. but reversal is a quadratic task on a single-tape turing machine too (afaik), so you're offloading O(n^2) operations to the construction of the initial state, and i don't think that's a proper reduction, so i didn't bother posting it.

math fag here, where should i start if i want to learn how to code?

CS isn't about coding.

Brainlet Academy
Or books, which are also easily found on the fucking wikis, either /g/ or Veeky Forums you piece of shit.

>tfw no CS general
there's an entire board dumbass

nevermind i got it.

OK try asking a question on /g/ such as

Consider the set [math]SD = \{e: ϕ_e(0) ↓ and (∀j < e)[ϕ_j(0) 6= ϕ_e(0)]\}[/math].

Shew that SD is contains no infinite recursively enumerable set.

sorry should be
[math]SD = \{e: ϕe(0) ↓ \wedge (∀j < e)[ϕ_j(0) \neq ϕ_e(0)]\} [/math]

please define your notation

[math]\phi_e[/math] is the eth Partial Recursive function

[math] ↓ [/math] means it halts on that input

it's still unclear. SD is just a set of integers then.

/g/ doesn't talk about Computer Science. They talk about building game machines.

>OK try asking a question on /g/ such as
Here you go

Yes and you are supposed to show that it does not have an infinite recursively enumerable subset

dunno then. seems like that would at least depend on the particular choice of mapping from functions to integers, but apparently not.

damn, i used to know a lot more about this stuff, but i'm not even sure why that's true.

I have a copy of this on the shelf. My theory of computation class was not quite as hardcore as that however, paging through it.