C(odemonkey) S(tudies) general

>>9062440
>>>/g/

>>9062440

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

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

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

>>9062755

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.

>>9062842
God dammit, you're right.

>>9062489

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

>>9062440
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

>>9065149

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

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

>>9065149

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.

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

>>9065212
CS isn't about coding.
>>>/g/

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

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

>>9065149
>>9065182

nevermind i got it.

>>9065345
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]

>>9065394
please define your notation

>>9065399

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

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

>>9065412

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

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

File: firefox_2017-07-26_23-48-39.png (8KB, 818x112px) Image search: [Google]

8KB, 818x112px

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

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

>>9065494

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.

File: ullman.jpg (36KB, 317x475px) Image search: [Google]

36KB, 317x475px

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.