Mathematics

6:00 PM

what I'm a little surprised by: The Entscheidungsproblem only wants a yes or a no. A finite automaton does that - it's build accepts or to not (depending on the input). But a turing machine makes more, it writes around on the input. Today in programs, this "side-effect" seems to be what we are really using - what the program prints on a string when given a starting input (string). The yes/no was the Entscheindungsproblem motivation. Is the capability of the turing machine an accident??

Henning Makholm

There are many ways to do this, and since they are fairly easy to prove equivalent it's not something one usually specify in details. You can either make each connective a part of the Turing machine's alphabet of symbols, or specify that the user of the machine has to encode everything as 0's and 1's first.

@NickKidman In order to be able to do everything computable, the Turing machine needs some scratch storage it can write to for internal uses. We're providing input to the machine by writing it on the scratch tape before we start the machine, but that is just because it simplifies the presentation. One could also have specified that the machine has a read-only input tape with its own separate read head that moves independently of the scratch read/write head.

This is necessary in order to define sublinear-space complexity classes -- the reason it's not done all the time is just because the other way feels simpler to formalize.

Ed Gorcenski

@JohnJunior True, but winning money makes a lucky man happy.

Nick Kidman

okay, ic. But I'm write in that we don't really program yes/no problems or halting problems in some twisted way, right? If I take a course in Java, I write programs from which I really want to give me the information which is stores, not merely the knowledge if it halts or not. And the output of a program, this is just that data from the memory of the turing machine, right?

John Junior

@EdGorcenski But a wise man does not care about gambling for money.

Gustavo Bandeira

@JohnJunior What does a wise man care for, then?

Henning Makholm

6:09 PM

Computability theory is (often) formulated mostly in terms of yes/no problems simply because these problems is easier to formulize mathematically. If we have a concrete problem with a richer set of output, we can convert it into a yes/no problem by instead considering the problem "What is the $n$th bit of the output of such-and-such instance of the problem?"

John Junior

@GustavoBandeira Wisedom.

Nick Kidman

"What is the $n$th bit of the output of such-and-such instance of the problem?" ... you mean if there are only two options for bit-outputs? Otherwise, this would be a bad yes/no question.

Henning Makholm

There are other approaches to computability whose basic units are functions from integer to integers instead of functions from bit strings to {yes,no}. We can handle them in the Turing machine formalism too, by considering the entire tape contents after the machine stops to be the output.

Gustavo Bandeira

@JohnJunior Isn't it wisdom?

Nick Kidman

mhm, okay

Henning Makholm

6:11 PM

@NickKidman Sure, "only two options" is pretty much the definition of "yes/no problem".

Nick Kidman

kk, I'm not into computability yet with the script I'm reading but soon

Henning Makholm

But you're reading about Turing machines?!

Nick Kidman

what?

John Junior

@GustavoBandeira Yes... I'm not wise at spelling :(

Henning Makholm

Computability (and complexity) is what Turing machines are for.

Nick Kidman

6:13 PM

I was reading some pages about a book about Computation a year ago. I constructed some finite automata, then I stopped reading it because I had to learn something else. Now that I'm reading logic and I'm capable of understanding the Entscheindungsproblem and the need for it, I connected some dots

that's why I'm interested in it. I asked because it occoured to me that a turing machine does a littlemore than answering yes not questions.

I have a script on computable functions, and I see there are some picutres which look like the diagrams for automata/turing machines - so yes, I'll probably be reading about them

you know, I posted the script last time

Gustavo Bandeira

@JohnJunior Dont worry, be happy.

John Junior

@GustavoBandeira That's what fun and games are for :-D

Henning Makholm

@NickKidman Okay, then I see. In fact in the original presentation Turing was quite concerned about getting a richer output from the machine than just a "yes/no" choice. It was only later that it was noticed that the presentation of the abstract computability theory could be simplified by making yes/no problems ("decision problems") the central player.

Nick Kidman

why? If he was interested in solving the Halting problem, which is a yes/no question?

something different: Why doesn't Löwenheim-Skolem imply incompleteness of infinite first order theories? Infinite models => no categoricity => structures with different truth values => sentences whose truth depends on semantics => true unprovable sentences

Peter Tamaroff

@HenningMakholm Hennig, do you thing you can help with some matrix stuff?

Gustavo Bandeira

6:19 PM

@NickKidman For automata theory, you need only a background on discrete mathematics, righ

Nick Kidman

I'd argue you need nothing

John Junior

hi @PeterTamaroff did you find the difference between : and | ?

Nick Kidman

it's like constructing board games :)

Peter Tamaroff

@JohnJunior I forgot to ask. Damn!

Nick Kidman

boards for board games

Henning Makholm

6:20 PM

@NickKidman You don't get interested in the halting problem without first being interested in computing machines for some other reason -- otherwise why worry whether they halt or not. My understanding is that Turing was motivated generally by understanding which computing processes can be explicitly and unambiguously specified in the first place -- and for that, an understanding of sub-processes that produce complex intermediate results is also needed.

John Junior

@PeterTamaroff next time

Henning Makholm

@PeterTamaroff Perhaps, though I'm probably not the resident linear-algebra expert.

Peter Tamaroff

@HenningMakholm Well, it's not really difficult stuff.

@HenningMakholm I just worked out the formula for the inverse of a given matrix

Say $$A=\left(\begin{matrix} a_{11}&a_{12}\\a_{21}&a_{22}\end{matrix}\right)$$

Michael Greinecker

WTF is going on with this guy. He is extremely unwilling to react to any criticism and posts trash all the time. Grrr.

Henning Makholm

@NickKidman No categoricity only means that there must be non-isomorphic models. Not that there has to be any sentence with different truth values in the models.

Peter Tamaroff

6:24 PM

Then $$A^{-1}=\frac{1}{\Delta}\left(\begin{matrix} a_{22}&-a_{12}\\-a_{21}&a_{11}\end{matrix}\right)$$ where $\Delta =a_{11}a_{22}-a_{21}a_{12}$

Now, I want to work out the same in $$\mathbb R^{3\times 3}$$

The method I'm using is setting this "matrix"

Ed Gorcenski

@MichaelGreinecker People like that tend to see the service as a resource to be consumed and thrown out, and care not about their contribution to its preservation.

Nick Kidman

if the truth values are the same, how are the models different? is it that they just have non-maching objects which fulfull the axioms?

@GustavoBandeira: How to recognize a physicist reading on complutation on a sunny day in a park: i.imgur.com/pgyGu.jpg

Henning Makholm

@PeterTamaroff Whoa. I find I'm at work with a browser where I don't have the chatjax bookmark available (and am loath to install it), so that is hard for me to read. Sorry.

Gustavo Bandeira

@NickKidman lol

Peter Tamaroff

@HenningMakholm math.ucla.edu/~robjohn/math/mathjax.html

@HenningMakholm OK, OK.

Ed Gorcenski

6:26 PM

@PeterTamaroff Are you just looking for the general form for a 3x3 inverse?

Peter Tamaroff

@EdGorcenski No, I want to find it myself.

..

Ed Gorcenski

Do you know of the trick of augmenting the matrix and using Gauss-Jordan elimination?

Peter Tamaroff

@EdGorcenski Yes.

Nick Kidman

@GustavoBandeira: I remember that day a friend had an accident in the lab and got some metal splinter in her eye. We were sitting at the hostpital waiting room for 3 hours, asking for some challenges to build automata which would recognize strings with 30 random 0's and 1's

Peter Tamaroff

@EdGorcenski Augmenting means making it a triangular matrix?

Why won't that render!?!?!?!?!?

Ed Gorcenski

6:28 PM

No, basically, it's a shorthand version, you append another matrix to your matrix like this:

Gustavo Bandeira

@NickKidman What you mean?

Ed Gorcenski

(A | I)

Peter Tamaroff

$$M=\left(\begin{matrix} a_{11}&a_{12}&a_{13}&1&0&0\\a_{21}&a_{22}&a_{23}&0&1&0\\a_{31}&a_{32}&a_{33}&0&0&1\‌end{matrix}\right)$$

@EdGorcenski Yes, I'm trying to TeX that

Now I need to get it in the form $(I|A^{-1})$

Ed Gorcenski

Right

Henning Makholm

@NickKidman The difference is just that there is no isomorphism between them. In general this would mean that both models contain some non-nameable objects that don't have a one-to-one correspondence with each other.

Peter Tamaroff

6:30 PM

So first I eliminate the first two columns by multiplyingout by $a_{21}a_{31}$, $a_{11}a_{31}$ and $a_{11}a_{21}$ and subtracting.

Nick Kidman

@GustavoBandeira: To get started, the picture with my arm depics a board (finte automaton) which accepts strings which contain the substring "1111". Just try it out. consider the string "00110011" and move around, starting from start. Then try "00001111". (in the first case, you will not make it to fin, in the other case you do - the automaton accepts it)

Peter Tamaroff

@Ed Right?

Gustavo Bandeira

@NickKidman I guess I'm not very able to do it, the only thing I know about automata theory is related to the first pages of Wolfram's NKS.

Ed Gorcenski

Well, you just perform gauss-jordan elimination steps. The first one would be to multiply the first row by $a_{31}/a_{11}$ and subtracting that from the third row

Gustavo Bandeira

In portuguese, there's a figure of speech called: Cacofonia.

It happens when the words you pronounced sounded like some other word, I guess that "Vary Able" is that.

Nick Kidman

6:32 PM

@GustavoBandeira: Yes, you are able to do it. Open the pic, move your finger to the "start" field and then say the numbers "00110011" to yourself and move the finger accordingly

Ed Gorcenski

Then, multiply the first row by $a_{21}/a_{11}$ and subtract that from the second row, etc.

Peter Tamaroff

@EdGorcenski Oh, OK.

Ed Gorcenski

When I say "multiply the first row", I don't mean actually multiply it in place

Nick Kidman

For "00110011" you'll move in boring circles. For "00001111" on the other hand, you'll make it to the end

Ed Gorcenski

I mean "subtract from the kth row some multiple of the first row"

Gustavo Bandeira

6:34 PM

@NickKidman If a 0 is found, I get back to the start, right?

Ed Gorcenski

Gauss-Jordan steps aim to annihilate sub-diagonal entries, starting with the last row in the first column, working upwards, then rightwards

Nick Kidman

I constructed it that way yes.

The arrows are as you choose

@HenningMakholm: k, thanks I think I get it.

Gustavo Bandeira

@NickKidman What's the meaning of this pic you just shown me? Why get to the end of it?

Nick Kidman

it's the automaton, which is designed to accept strings which contain "1111". If you go through a string "01010100111100101010", and you move according to it on the board, and it happens to contain "1111", then at the end, you will be at "fin".

it is a procedure which checks if a string contains "1111". The user doesn't have to thing, just move his finger on the board according to the next digit in the string

think*

Gustavo Bandeira

@NickKidman It's like a filtering device?

Nick Kidman

6:38 PM

if you will

Gustavo Bandeira

@NickKidman This is cool! What else could be made with automatons?

Nick Kidman

it's like a key-code on an electric door. Say the code is "10101" and if the user presses "open" and the automaton state is a fin, he will be let in

Gustavo Bandeira

@NickKidman Are automatons different of Celular Automatons?

Nick Kidman

I'm used to german terminology, what I talk about here is a finite automaton or finite state machine http://en.wikipedia.org/wiki/Finite_state_machine

Peter Tamaroff

@EdGorcenski This matrix is getting ridiculously huge.,

So now I eliminated the second and third coeff. got $a_{11},0,0$

Now I want to eliminate the $3,2$ right?

Gustavo Bandeira

6:43 PM

I found this on Mathematica:
http://reference.wolfram.com/mathematica/ref/CellularAutomaton.html

But they don't seem to be the same thing.

Peter Tamaroff

Then I normalize everything and I'm done.

Nick Kidman

@GustavoBandeira: From what I understand, these are capable of much more than finite state machines

Gustavo Bandeira

@NickKidman I have this book: Introduction to Automata Theory, Languanges and Computation by: John E. Hopcraft, Rajeev Motwani, Jeffrey D. Ullman

Henning Makholm

@GustavoBandeira "Automaton" is a general term for a discrete system that develops in time according to some fixed rule (usually where the rule has a finite description). Cellular automata and the finite automata Nick speaks about are two different specializations of this general concept.

Nick Kidman

@GustavoBandeira: I think Steven Wolfram is popular for being involved in discovering that there is a celular automaton, which is equivalent to a turing machine

Gustavo Bandeira

6:45 PM

@NickKidman But I still didn't read it because it says I need some background in discrete mathematics.

Nick Kidman

@GustavoBandeira: I'd suggest you take a pen and a paper and build a finite automata/finite state machine which does something specific. It's fun. Like draw one which accepts string with "010" substrings, but which goes to a new terminal 'death field', as soon as there is a substring "11".

Henning Makholm

@GustavoBandeira From the title, it seems that a large part of what it will introduce you to IS discrete mathematics. The necessary background may well be absolute basics that you know already but just never knew had the fancy name of "discrete mathemtics".

Peter Tamaroff

@GustavoBandeira Always give it a try first!

Gustavo Bandeira

@HenningMakholm This is one of things that let me VERY curious. All I see are plots that grow according to some pattern - but I guess that there may be something very interesting there.

Ed Gorcenski

@PeterTamaroff First eliminate $a_{31}$, then $a_{21}$ then $a_{32}$. The matrix will be in upper triangular form

Gustavo Bandeira

6:48 PM

@HenningMakholm btw, I've heard discrete math is harder than calculus, is it true?

@NickKidman Yep. =)

Peter Tamaroff

@EdGorcenski Yes.

Ed Gorcenski

Then, eliminate $a_{23}$ and $a_{13}$. Finally, eliminate $a_{12}$

Henning Makholm

In the (1D) cellular-automata case, the point is that each line depends on what is in the line above it in a fairly simple (and local!) way.

Ed Gorcenski

And yes, the result will get quite ugly

However, you will soon realize that every element of the inverse has a $1/\Delta$ term, just as in the 2x2 case.

Henning Makholm

@GustavoBandeira I don't think so -- even to the case that one can compare the difficulties of two areas that each span a wide range of sophistication levels, I don't see any reason to consider discrete math inherently more difficult than calculus/analysis.

@GustavoBandeira If you know Conway's Game of Life, that's a fairly prototypical cellular automaton on a two-dimensional square grid.

Gustavo Bandeira

6:52 PM

@HenningMakholm Yep, I know it. I just don't know what it means - considering it may have a meaning.

Transcript for

$Mathematics$ Mathematics