The h Bar

1:00 AM

and q is the current state of the machine, because $K$ is the information it currently has access to, which depends on the tape and where it is on the tape

Bernard Meurer

@heather AND on how far into the program it is

heather

but i thought that was k

oh...

Bernard Meurer

Wait, I screwed up

heather

huh

Bernard Meurer

What I wanted to say is

$k$ is how far into the program it is

heather

1:02 AM

okay.

Bernard Meurer

but just wanted to note that $q$ also depends on $k$

heather

$q$ also depends on $k$?

Bernard Meurer

Hmm, I'm just confusing you more, ignore that

we'll get to it

heather

okay

0celo7

@BernardMeurer what the hell are we doing?

Bernard Meurer

1:03 AM

@0celo7 CS

cs.cornell.edu/courses/cs4820/2012su/handouts/turingm.pdf

heather

so anyway, x is the program, q is the state of the computer as it is running the program, and k is how far it is into the program.

Bernard Meurer

We're on Def.2 feel free to join

heather

Next sentence: The string x is required to begin with . and end with t. The position k is required to satisfy 0 ≤ k < |x|.

Bernard Meurer

This is the closest I've been to studying something I enjoy ever since I got into college

0celo7

:(

ACuriousMind

1:04 AM

@BernardMeurer :(

Balarka Sen

@ACuriousMind Nice avatar.

heather

@BernardMeurer, I'm sorry =(

Balarka Sen

Is it inspired by Gromov? :P

0celo7

God dammit

I knew it

ACuriousMind

@BalarkaSen lol, maybe that conversation did influence me subconsciously

Bernard Meurer

1:05 AM

meh, it;s fine

heather

not really

but okay

0celo7

Holy crap I thought ACM was heather just now

Bernard Meurer

@ACuriousMind How do we do those funky charactes on def 2 of LaTeX?

heather

@0celo7, wait, what? We have very different avatars.

Bernard Meurer

$\triangleright$

0celo7

1:06 AM

I double checked the name

heather

$\triangleright$

0celo7

It said "heather" with 100% certainty

Bernard Meurer

$\sqcup$

Okay

Got it

heather

wait how do you do the second one?

ACuriousMind

@BernardMeurer You mean $\sqcup$ and $\triangleright$?

0celo7

1:07 AM

Hmm.

heather

@ACuriousMind, $\triangleright$

Bernard Meurer

The string $x$ is required to begin with $\triangleright$ and end with $\sqcup$. The position $k$ is required to satisfy $0 \leq k < |x|$.

ACuriousMind

It's triangleright, I always mix up the order there

Bernard Meurer

Typo, @heather the other one is \sqcup

heather

okay, thank you

0celo7

1:08 AM

Why do you ever need a right facing triangle @ACuriousMind

$\sqcup$

Normal subgroup.

thank you

I'm stupid.

@0celo7 yep

1:08 AM

@heather So, do you get that sentence

heather

okay, so $x$ must begin with $\triangleright$

Bernard Meurer

and end with $\sqcup$

heather

so the first character in $x$ is represented by $\triangleright$?

and the last character by $\sqcup$?

Bernard Meurer

@heather So, you know how in Python some words are part of the language and you can't use them for your variables?

Like print or def

heather

sure, yeah

Bernard Meurer

1:09 AM

(You actually can, but that's nasty and we will ignore it for the sake of this example)

heather

sounds very nasty

if x = asdf, would $\triangleright$ = a and $\sqcup = $f?

Bernard Meurer

$\triangleright$ and $\sqcup$ here are like that, they are special language elements that indicate the beginning and end of a program respectively

heather

oh...huh, okay.

0celo7

@ACuriousMind How does one see that $|a|<b$ means $-b<a<b$

Bernard Meurer

@heather The way we are defining things here $x=asdf$ isn't a valid program

@heather Can you make it valid for me?

heather

1:11 AM

@BernardMeurer, it isn't? Why not?

Bernard Meurer

Tip. It needs a start and finish, just like good stories

heather

x = $\triangleright$asdf$\sqcup$?

0celo7

@BernardMeurer can you help with python in 30 mins?

Bernard Meurer

@heather Precisely :) (fix the LaTeX though, extra $)

@0celo7 Yes, call me on Skype

Balarka Sen

@0celo7 $a = \sgn(a) |a|$.

not gonna edit that

heather

1:13 AM

okay, that makes sense now. so then, $0\leq k < |x|$...

0celo7

@BalarkaSen Ok I know why it's true, but it doesn't click.

heather

k is the spot in the tape, right, and x is the program, and |x| is the length of x

Bernard Meurer

@heather Tip. Our tape is not doubly infinite, it's infinite in one direction only

0celo7

I mean surely you think I could prove that?

Bernard Meurer

@heather YES, but the last element of $x$ is always?

Joshua Lamusga

1:14 AM

Are we talking about Turing machines :P

Balarka Sen

I couldn't make out if you were asking for intuition or wanted me to prove it for you

Bernard Meurer

@JoshuaLamusga Yes

heather

so the spot in the tape can't be anything less than 0, and it can't be x or anything after that

Balarka Sen

$|a|$ is the distance from $0$ to $a$. Draw it.

heather

@BernardMeurer, $\sqcup$

0celo7

1:14 AM

Yeah I did that in high school

Bernard Meurer

@heather YES!

So do you see why it $k<|x|$?

Jesus Christ

heather

so if you have x = $\triangleright$asdf$\sqcup$ then $k$ can be 0, representing $\triangleright$, 1, representing a, 2, representing s, 3, representing d, and 4, representing f, but not 5 representing $\sqcup$, right?

Bernard Meurer

My life is a lie

I should have picked CS all along

Why am I in engineering?

What am I doing?

heather

@BernardMeurer, I'm probably being dumb, but can't you switch majors?

Bernard Meurer

Daniel was right

@heather yes. In my case it's complicated

GPhys

1:16 AM

@0celo7 hi

0celo7

hi

heather

@BernardMeurer, you know, I think you'd be a great teacher. A teacher of complexity theory...

=)

GPhys

@0celo7 come to room, to talk about IST

$Mathematics$ Room for GPhys and 0celo7

Bernard Meurer

@heather Yes! Precisely!

@heather Ha, thank you

heather

@BernardMeurer, are we talking about college or complexity theory now, I've lost track =P

Bernard Meurer

1:18 AM

@heather Computability and college respectively

heather

Aha, gotcha

so I guess, I understand the how, but not the why.

why can $k \neq \sqcup$?

Bernard Meurer

Keep in mind, we haven't even glimpsed complexity yet. For us to understand what is difficult or easy to compute we must first understand what it means to compute something

heather

true, yes. =)

good to start with the basics

@BernardMeurer, is it because $\sqcup$ means stop? so $k$ never reaches it?

(loosely speaking)

Bernard Meurer

@heather Oh, wait, my bad, $k<|x|$ just because $x$ is indexed from 0, and $|x|$ is length and not the largest $n$ in $x_n$

heather

oh, okay

Bernard Meurer

1:20 AM

@heather Nah, it reaches it, note that $\sqcup$ just means end, and not necessarily stop

heather

okay.

Bernard Meurer

IMPORTANT

We won't be using the word stop to mean what you wanted to mean there

that's for plebs

We now use halt

heather

okay

Bernard Meurer

The program doesn't stop, it halts

heather

does that have to do with the halting problem?

Bernard Meurer

1:21 AM

YES

Joshua Lamusga

That's why they share the same word, yes.

Bernard Meurer

It's a fundamental problem in computability

heather

okay

cool!

next sentence:

If M is a Turing machine and (x, q, k) is its configuration at any point in time, then its
configuration (x0, q0, k0) at the following point in time is determined as follows. Let (p, σ, d) = δ(q, xk).

maybe we should go back to def 1 now so we know what $\delta$ is

or not yet?

Bernard Meurer

$(x', q', k')$ at the following point in time is determined as follows. Let $(p, \sigma, d) = \delta(q, x_k)$.

heather

what is "the following point in time"?

Bernard Meurer

1:24 AM

$\delta : K \times \Sigma \rightarrow (K \cup \{\text{halt, yes, no}\}) \times \Sigma \times \{\leftarrow,\rightarrow, −\}$

@heather It's it's next step basically

heather

@BernardMeurer, okay

Bernard Meurer

If we're currently in a state $foo$ then the next state is $foo'$

heather

and to determine foo'

Bernard Meurer

We will get there, keep reading a bit

heather

okay, so what is p, $\sigma$, and d?

Bernard Meurer

1:26 AM

@heather Okay, buckle up, let's decipher the $\delta$

heather

ready

0celo7

@heather Prove: if $|x|<\epsilon$ for all $\epsilon>0$, then $x=0$.

Bernard Meurer

All I want you to understand here, is that $\delta$ takes in a state $q\in K$ and a letter $x\in \Sigma$ and yields a triplet $(p, \sigma, d)$

Joshua Lamusga

This conversation is very interesting and I really don't want to interrupt it, but could anybody help explain the Coriolis Effect? I know it's an adjustment in equations used to offset conceived deflection in a rotating coord. system (thanks, Wikipedia), but everything there implies it's fictitious and yet examples with wind say the air is deflected by the Coriolis effect, like it's a force.

0celo7

Much easier (and much more useful) than what Bernardo is trying to teach you.

ffahim

1:29 AM

Gd morning guys...

Bernard Meurer

@heather Now what is $(p, \sigma, d)$, let's go through it

heather

@BernardMeurer, right

Bernard Meurer

@heather Let me just make sure I get this 100% right

heather

okay

Bernard Meurer

$d$ will be the movement the machine will do, $(\leftarrow, -, \rightarrow)$

0celo7

1:32 AM

Welp, getting ignored left and right tonight

heather

goes left, stays still, goes right

Bernard Meurer

So, it either goes left, does nothing, or goes right

heather

@0celo7, no, I saw, I just have no idea how to do that

Bernard Meurer

Yes, note that some models of turing machines do not allow it to stand still

0celo7

@heather Does it make sense at least?

heather

1:32 AM

okay

ACuriousMind

@JoshuaLamusga Ah, a force can be fictitious and still be a force

heather

@0celo7, yes, I think...well, actually, how, if x < epsilon and epsilon is less than 0 can x = 0?

Bernard Meurer

@heather $p$ is the new internal state after we act on the data we read

0celo7

@heather did I forget epsilon positive?

heather

@BernardMeurer, that makes sense

@0celo7, ?

Joshua Lamusga

1:34 AM

@ACuriousMind But the Coriolis effect is quite literally not a force.

0celo7

@ACuriousMind ????

Bernard Meurer

@heather Focus on this

heather

@BernardMeurer, right, sorry.

Bernard Meurer

Heck, what's the $\sigma$ again

Let me check

heather

So $p$ is the new information known, $d$ is the movement, and let me guess $\sigma$ is whether or not it halts/spits out yes/no

ACuriousMind

1:35 AM

@JoshuaLamusga Why not? When I describe the physics on Earth in a coordinate system that's fixed at a point on earth (and therefore actually moving since the earth rotates), then in that system I will see the Coriolis force.

Bernard Meurer

@heather that would be contained in $p$ I think since we defined $$\delta : K \times \Sigma \rightarrow (K \cup \{\text{halt, yes, no}\}) \times \Sigma \times \{\leftarrow,\rightarrow, −\}$$

So it basically becomes part of the state

AH

I remembered

heather

@Bernard, the state contains the halt/yes/no, okay

0celo7

@heather Oh, clearly I meant $\epsilon>0$ :P

Bernard Meurer

$\sigma$ is the symbol to write in the place of the old one before we move :)

heather

?

The old one...

oh, oh, gotcha! that makes sense now.

0celo7

1:37 AM

So if we have a number whose absolute value is smaller than any positive number, it must be zero!

Bernard Meurer

@heather Got it?

0celo7

reasonable, no?

heather

@BernardMeurer, yes, I think so.

ACuriousMind

@JoshuaLamusga I think the gif at the start of the Wikipedia article demonstrates it rather well

Bernard Meurer

So after we act $\delta$ we overwrite the current symbol with $\sigma$, our new state is $p$ and we perform a movement $d\in\{\leftarrow,\rightarrow, −\}$

heather

1:38 AM

right, yes!

this is making sense!

Bernard Meurer

9 mins ago, by Bernard Meurer

All I want you to understand here, is that $\delta$ takes in a state $q\in K$ and a letter $x\in \Sigma$ and yields a triplet $(p, \sigma, d)$

Understand this now?

$$\delta : K \times \Sigma \rightarrow (K \cup \{\text{halt, yes, no}\}) \times \Sigma \times \{\leftarrow,\rightarrow, −\}$$

heather

Yeah!

Bernard Meurer

FUCK YEAH GIRL

NEXT SENTENCE

heather

If M is a Turing machine and (x, q, k) is its configuration at any point in time, then its
configuration (x0, q0, k0) at the following point in time is determined as follows. Let (p, σ, d) = δ(q, xk).

Joshua Lamusga

@ACuriousMind I've seen that gif and understand it thoroughly. I understand that when you throw a ball in a straight line while on a merry-go-round that it appears to curve opposite your direction of motion and this is the Coriolis Effect. But that means its illusory. I don't understand why air (not rotating with Earth) will start spinning around a low pressure system, for example, if the Coriolis Effect is visual. I hope I'm wording it right.

Bernard Meurer

1:40 AM

@heather Fix the LaTeX, I'm a lazy man

0celo7

@BernardMeurer ...

Joshua Lamusga

That is, you should be able to break down the cyclic motion of air into other forces besides the Coriolis Effect. Otherwise, it is a force and that violates the definition of it being fictitious.

Sir Cumference

Cool, so degenerate gases finally make (mostly) sense

ACuriousMind

@JoshuaLamusga For an observer not rotating with the Earth, the air is moving in a straight line. But we're standing on earth, rotating with it. So our perspective is that of the fixed red dot in that gif.

Bernard Meurer

@0celo7 Computer Science is da bomb man

heather

1:41 AM

If $M$ is a Turing machine and $(x, q, k)$ is its configuration at any point in time, then its configuration $(x_0, q_0, k_0)$ at the following point in time is determined as follows. Let $(p, \sigma, d) = \delta(q, x_k)$.

okay, we've got our nice, dandy black box

and that configuration

Joshua Lamusga

@ACuriousMind That fits the definition, but there are pictures of hurricanes from space and they are actually spiraling.

Bernard Meurer

@heather Now we're showing what happens when we move our machine on the tape

Sir Cumference

@ACuriousMind Isn't it just a fictional force?

Just like centrifugal force

ACuriousMind

@JoshuaLamusga Everything that makes photos from space is still rotating with the earth, i.e. not an inertial observer either

heather

then the next configuration is determined by taking $\delta$ of the current state and the , letter at the position in the program. Then you get a new state, a new letter to overwrite the current letter, and a movement to the next letter.

ACuriousMind

1:42 AM

@SirCumference I did never say it wasn't.

0celo7

@ACuriousMind Are you saying hurricanes aren't actually spinning?

Sir Cumference

@ACuriousMind Do fictitious forces fit the traditional definition of a force?

Bernard Meurer

@heather We are reaching the point where we understand how a Turing machine works

Just a bit more

heather

@BernardMeurer, so with that triplet of info, you can basically do $n+d$, sort of, to get the new $n$, and you get a new state for $q$, and then $x$ the new letter is $\sigma$, right?

Bernard Meurer

@heather You can't multiply the $ \{\leftarrow,\rightarrow, −\}$ by a scalar :p

heather

1:44 AM

hmm, yeah =P

Bernard Meurer

You move one to the left, one to the right of you sit around

heather

that's what I meant =)

ACuriousMind

@0celo7 What does "actually" mean here? For an inertial observer, the air is moving in straight lines and the earth is rotating "under it", just like with the Foucault pendulum.

heather

so now we have our next state! And we carry on. Wonderful! The tape is moving (or the machine is moving, whichever).

Okay, next sentence:

0celo7

@ACuriousMind Give an example of an inertial observer

heather

1:46 AM

The string $x_0$ is obtained from $x$ by changing $x_k$ to $\sigma$, and also appending $\sqcup$ to the end of
$x$, if $k = |x| −1$.

ACuriousMind

@SirCumference My definition of a force (in a given reference frame) is $F=ma$, and they do fit that. Forces are not frame invariants.

Sir Cumference

@ACuriousMind Eh, that won't hold in all physics...

heather

okay, so the next character is obtained by changing the current character to $\sigma$ and then if k is at the end, basically, you append the end sign.

so what we just described.

0celo7

@SirCumference what?

ACuriousMind

@0celo7 Someone sitting at the center of the earth, not rotating :P

heather

1:48 AM

@BernardMeurer, the next sentences describe basically what we talked about, how you get the new state from using $\delta$

ACuriousMind

@SirCumference It holds in Newtonian mechanics, which is what we're concerned with when discussing the Coriolis force, no?

Nothing ever holds in "all of physics", that's a silly objection

0celo7

@ACuriousMind they would think hurricanes don't spin?

Sir Cumference

@ACuriousMind Well then, how does Newton's third law apply to the Coriolis force?

heather

so the next bit

0celo7

I'm calling so much bullshit

heather

1:49 AM

A computation of a Turing machine is a sequence of configurations $(x_i, q_i, k_i)$, where $i$ runs from $0$ to $T$ (allowing for the case $T = \infty$)

Bernard Meurer

If $M$ is a Turing machine and $(x, q, k)$ is its configuration at any point in time, then its configuration $(x_0,q_0,k_0)$ at the following point in time is determined as follows. Let $(p, \sigma, d) =
\delta(q, x_k)$. The string $x_0$ is obtained from $x$ by changing $x_k$ to $\sigma$, and also appending $\sqcup$ to the end of $x$, if $k = |x| −1$. The new state $q_0$ is equal to $p$, and the new position $k_0$ is equal to $k −1$, $k + 1$, or $k$ according to whether $d$ is $(\leftarrow,\rightarrow,-)$, respectively. We express this relation between $x,q,k$ and $(x_0, q_0, k_0)$ by writi…

heather

that satisfies:
• The machine starts in a valid starting configuration, meaning that q0 = s and k0 =0.
• Each pair of consecutive configurations represents a valid transition, i.e. for 0 ≤ i < T, it is the case that (xi, qi, ki) M−→ (xi+1, qi+1, ki+1).
• If T = ∞, we say that the computation does not halt.
• If T < ∞, we require that qT ∈ {halt,yes,no} and we say that the computation halts.

Bernard Meurer

@heather Read that bit very carefully

it is crucial

heather

okay

so first, a computation, a sequence of these states where $i$ runs from 0, the beginning of the program, to $T$, and $T$ can equal $\infty$

that makes sense. if you made a set that had all the states, i is just the index number of a particular state.

is T kind of like what k equals when you reach the $\sqcup$?

or no?

ACuriousMind

@SirCumference The third law is about objects exerting forces on each other. Fictitious forces are not exerted by anything, so it just doesn't have anything to say about them.

Sir Cumference

1:53 AM

@ACuriousMind But..but...that's...

Joshua Lamusga

I understand the Coriolis Effect thanks to scijinks.jpl.nasa.gov/coriolis.

ACuriousMind

@0celo7 Yes, they would see a straight(-ish) airflow with an Earth spinning under it.

Bernard Meurer

@heather Pretty much, yes

Sir Cumference

@ACuriousMind The Coriolis force literally only exists because of Newton's first law

heather

and then the first configuration must have q0 equal to s, right, s is defined as the starting state for information

and k obviously is 0

0celo7

1:54 AM

@ACuriousMind I reject that with all my being. Proof?

I seriously mean that

Bernard Meurer

@heather Remember, the tape is infinite, so is $\Sigma^*$, you may sometimes never reach $\sqcup$

0celo7

I do not believe that for one second

heather

@BernardMeurer, huh, okay

so that is when T = $\infty$?

Bernard Meurer

Yep

ACuriousMind

@0celo7 Do you reject the Foucault pendulum? It's the very same effect, just on a much grander scale?

Sir Cumference

1:55 AM

Are we accepting anything resulting from Newton's first law as a "force"?

Bernard Meurer

@heather You know for a fact it won't ever halt there

user218912

@SirCumference what?

0celo7

@ACuriousMind Never heard of it.

Sir Cumference

@obe We're talking about fictitious forces

heather

@BernardMeurer, right, those last two bits make sense: if $T = \infty$, then it never halts, if it is less than infinity, then it does

Joshua Lamusga

1:56 AM

Basically, the Earth spins with some angular velocity. Air spins above and with it. When air moves laterally from the equator, it's moving to a smaller radius. All that extra tangential speed causes it to move left/right. This deflection is also considered part of the Coriolis Effect, which can probably be proven with some formulas somewhere, but that's good enough for me.

user218912

I know.

Bernard Meurer

@heather :)

heather

and the information state at $T$ must equal halt, yes, or no?

Sir Cumference

@obe The Coriolis force is literally just Newton's first law in action.

Nothing special is happening

heather

or is that wrong?

ACuriousMind

1:56 AM

@SirCumference What? The first law is the assertions that inertial frames exist?

user218912

@SirCumference I know that I'm saying what you said first doesn't make any sense to me.

user218912

^

Bernard Meurer

@heather Perfect

Sir Cumference

@ACuriousMind No, I'm saying that for the Coriolis force to not exist, an actual force would need to be applied to the object

0celo7

wtf is happening

heather

1:57 AM

@BernardMeurer, so the second point it has to follow is what I don't quite follow, then

Each pair of consecutive configurations represents a valid transition, i.e. for $0 \leq i < T$, it is the case that $(x_i, q_i, k_i) M\rightarrow (x_i+1, q_i+1, k_i+1)$.

ACuriousMind

@0celo7 You've never seen a rather large pendulum where some things it can knock down are arranged around it in a circle? It then is released in a straight line and, depending on where you are on earth will rotate its plane of motion in the course of a day.

user218912

@SirCumference how is that what you said before and what?

Sir Cumference

@obe I realize what I said before made no sense

I'm out of it

Anyway, back to thinking straight

ACuriousMind

@SirCumference I don't understand that sentence, I'm afraid.

0celo7

@ACuriousMind No, where would such a thing be?

heather

1:59 AM