My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news


Thanks Tree3Thanks
Reply
 
LinkBack Thread Tools Display Modes
June 8th, 2017, 10:41 AM   #11
Senior Member
 
Joined: Aug 2012

Posts: 1,510
Thanks: 364

Quote:
Originally Posted by zambod View Post
I've been trying to think about why you find game semantics so exotic when researchers working on it intend it to be a more intuitive model for computation than Turing Machines.
One clue is that when one Googles the subject, one finds a Wiki page that appears to have been written by the author of the paper, and whose list of references consists of a long list of the author's own work. This observation is confirmed by several commenters on the Talk page. It's not just me.

But whereas earlier you seemed to be asking questions and we seemed to be having a conversation; in your latest post you seem to be grinding an ax.

You can study anything you like. You don't need my permission.

I wonder why you didn't bother to respond at all to any of the substantive points I made about ordinal models of computation, oracles, Chaitin's incompleteness results, and so forth.

Quote:
Originally Posted by zambod View Post
Have you studied programming computable functions (PCF), Martin Lof's type theory, linear logic and the early literature on game semantics? The first three are each a set of rules that can be listed on a single page. You can find basic texts on these subjects by Googling: <subject name> pdf
If you've studied the "early literature on game semantics" then you don't need my advice.

Are you conversating or ax grinding here? Honestly this last post of yours seems to come from left field. I already suggested Reddit and Stackexchange as more suitable venues for the technical details of your question. I offered some thoughts of my own, which seems to have disappointed you.

Last edited by Maschke; June 8th, 2017 at 10:50 AM.
Maschke is offline  
 
June 8th, 2017, 10:54 AM   #12
Newbie
 
Joined: Mar 2016
From: Alabama

Posts: 18
Thanks: 0

Quote:
Originally Posted by Maschke View Post
One clue is that when one Googles the subject, one finds a Wiki page that appears to have been written by the author of the paper, and whose list of references consists of a long list of the author's own work. This observation is confirmed by several commenters on the Talk page. It's not just me.
Game semantics was not originated by Japaridze. Did you search for "game semantics" or "computability logic"?

Quote:
Originally Posted by Maschke View Post
I wonder why you didn't bother to respond at all to any of the substantive points I made about ordinal models of computation, oracles, Chaitin's incompleteness results, and so forth.
I'm planning to. I'm very excited about Yamada's paper, which you will note comes out of Oxford, not wherever Japaridze teaches. The part of your post that interests me the most is why people who are knowledgeable about computer science but new to game semantics might find the subject counterintuitive. This is because that's an area where I see a marginal advantage for myself in the future as a person who has put some effort into studying the subject, though I'm by no means a knowledgeable beginner, let alone an expert.

Last edited by zambod; June 8th, 2017 at 10:57 AM.
zambod is offline  
June 8th, 2017, 10:58 AM   #13
Senior Member
 
Joined: Aug 2012

Posts: 1,510
Thanks: 364

Quote:
Originally Posted by zambod View Post
Game semantics was not originated by Japaridze. Did you search for "game semantics" or "computability logic"?
Why do you care? You've clearly switched interests from wanting to talk about some technical subject, to wanting to know why I haven't got any interest in it. I haven't got any interest in it because the Wiki page on CoL shows that it's a niche subject at best, far beyond my expertise and very far from any of my interests.

Quote:
Originally Posted by zambod View Post
I'm planning to. I'm very excited about Yamada's paper, which you will note comes out of Oxford, not wherever Japaridze teaches. The part of your post that interests me the most is why people who are knowledgeable about computer science but new to game semantics might find the subject counterintuitive. This is because that's an area where I see a marginal advantage for myself in the future as someone who has put some effort into studying the subject, though I'm by no means a knowledgeable beginner, let alone an expert.
You should follow whatever path makes sense to you. I'm not knowledgeable about computer science. I Googled around and came to some informal conclusions. Which, for the record, I reiterate.

You seem to want me to care about something I'm not planning to care about. I'm just some anonymous person on the Internet. Why do you care what I care about?

I did take the trouble to give you some leads into what serious thinkers think about the realm just beyond computability. If Chaitin, Turing, and Gödel don't appeal to you, I don't have anything to add.

Last edited by Maschke; June 8th, 2017 at 11:08 AM.
Maschke is offline  
June 8th, 2017, 12:53 PM   #14
Newbie
 
Joined: Mar 2016
From: Alabama

Posts: 18
Thanks: 0

Quote:
Originally Posted by Maschke View Post
Yes, I noticed this in something I read somewhere. If $P$ is a unary predicate then the expression $\exists x P(x)$ asserts the existence of something but does not provide a recipe for cooking one up. Constructivists are people who are bothered by this.

On the other hand, computation is inherently constructive. It's exactly the study of everything we can construct using algorithms.
Yes, but this presupposes a definition of computation that excludes real applications that can only be described as "computation".

Quote:
Originally Posted by Maschke View Post
So I am arguing that the link between computation and constructive math is more circumstantial than philosophical. In other words computation just happens to be about recipes, and constructivists like recipes. But I think the study of computation is itself agnostic to the philosophy. If computation turned out to involve nonconstructive elements then the computer scientists would just do that. They wouldn't be bothered by using nonconstructive math if that's what they needed to do to study computation. Whereas the constructivists would be annoyed.

Does that make sense?

I have a datapoint to support this opinion later.
I agree.

Quote:
Originally Posted by Maschke View Post
Yes, I think I understand that. That's why for example determining if a floating point number is zero is not computable. Because in an idealized (infinite memory) implementation, no matter how many 0's you see, you can never be sure whether the next digit will be 1. So floating point numbers are conceptually broken. You can't map the mathematical (nonconstructive) real numbers onto computations.
Is the mapping from N to N you mentioned earlier is uncountably infinite? Because even Godel's incompleteness deals with countable things AFAIK.

Quote:
Originally Posted by Maschke View Post
Procedures that don't halt. I don't know anything about those. So maybe this is something people study.
Have you read about recursively enumerable languages?

Quote:
Originally Posted by Maschke View Post
I do know that there is a concept in math called "definable but not computable." A number is computable if there is an algorithm that cranks out its decimal (or binary) digits. A number is definable if it can be uniquely characterized in the language of first-order Peano arithmetic (or some other system, which may give you a different notion of definability).

It's not hard to whip up a real number that is definable but not computable. One such is Chaitin's $\Omega$. https://en.wikipedia.org/wiki/Chaitin%27s_constant

This number is essentially a bitstring where the n-th bit tells you whether or not the n-th Turing machine (in some particular encoding) halts. This number can not be computable else we'd solve the halting problem. But it's perfectly well definable, I just defined it. (Exercise for the reader to figure out how what I said makes it "definable in first-order Peano arithmetic." That's beyond the limits of my knowlege).
IIRC the axioms of Peano arithmetic define one number and a successor function that generates all other numbers. The procedure of applying the successor function never terminates, making the total set of entities defined under Peano arithmetic uncomputable. The Halting problem is recursively enumerable, and the natural numbers are recursively enumerable, so that makes sense. Am I on the right track?

Also, Chaitin's constant is very interesting. I don't know about it before.

Quote:
Originally Posted by Maschke View Post
Now what's interesting is that Chaitin used his ideas to prove Gödel's incompleteness theorems in purely information-theoretic terms. So we're actually in the realm of Gödelean incompleteness here.
I know I've read a pdf on this before. Found it: https://www.andrew.cmu.edu/user/avig...andi_notes.pdf

Quote:
Originally Posted by Maschke View Post
And here is something not too well known. Say you have an axiom system for arithmetic (theory of the natural numbers). We know it's incomplete, so there's some statement we can neither prove nor disprove. So we pick a truth value arbitrarily and add that as a new axiom. Now we have a NEW axiom system (the original one plus the independent statement or its negation). But this new system must ALSO be incomplete ... so we can add another axiom ...

You can see that we are going to get an infinite hierarchy of axiom system that kind of branch out in all directions. And do you who studied this? None other than Turing. His doctoral dissertation was about "Ordinal models of computation," in which he used the mathematical theory of the ordinal numbers to keep track of the structures you get when you keep extending axiom systems.

https://en.wikipedia.org/wiki/System...ed_on_Ordinals

This is related to oracles. You assume you have a magic box that computes something noncomputable, and you see what you get.

So Gödel, Turing, and Chaitin are all over this mysterious realm of extensions beyond what's computable. And I believe this is what you are talking about.

Tell me if anything I've written is on target.
I don't know. I hope so, because now I'm going to have to read up on it. (I forgot too much.)

Quote:
Originally Posted by Maschke View Post
I read that section of the page and I think you read more into that quote than I did. But I'm really unfamiliar with formal approaches to computation although I've heard Hoare's name.
I was pushing a very modest claim about a well known mapping of imperative languages in terms of lattice theory not having termination hardcoded into it at any point.

Quote:
Originally Posted by Maschke View Post
I have the same question myself. A web browser obviously does not halt. It has no way of knowing whether the user will click on something in five minutes or whether the world has ended and there will be no more clicks.

So is a web browser not a computation in the sense of computer science? In which case, what is it?
A recursively enumerable language, probably. I guess you could say it is not a "computation" in the sense that a web browser is not an algorithm designed to compute the value of any one specific answer. But it is still a mathematical structure that can be elucidated in Hoare logic, right?

Quote:
Originally Posted by Maschke View Post
I wonder if the business about oracles and such is a step in that direction. We do go beyond computability by allowing one new noncomputable thing at a time.

But in math, we have a LOT of uncomputable things. Uncountably many. Too many to be accounted for in ANY possible formal system of symbol manipulation. Those kinds of systems are inherently countable.

So there's three levels:

* Computable.

* Definable but not computable. Extending axiom systems one new statement at a time. Chaitin's ideas. Oracles.

* Full mathematical ontology. Uncountably many real numbers, existence without recipes.
Level 3 is beyond my ambition. Since I asked for computability to be extended from level 1 to 2, I guess I should study recursively enumerable languages. What do you think? (Edit: "Post's theorem shows that RE, together with its complement co-RE, correspond to the first level of the arithmetical hierarchy." https://en.wikipedia.org/wiki/Recurs...rable_language)

Anyone who isn't thinking of discussing game semantics should ignore the rest:

(For anyone who might be put off by my posts in this thread, this is what Wikipedia says on the history of Game Semantics:

Quote:
In the late 1950s Paul Lorenzen was the first to introduce a game semantics for logic, and it was further developed by Kuno Lorenz. At almost the same time as Lorenzen, Jaakko Hintikka developed a model-theoretical approach known in the literature as GTS. Since then, a number of different game semantics have been studied in logic.

Shahid Rahman (Lille) and collaborators developed dialogic into a general framework for the study of logical and philosophical issues related to logical pluralism. At around 1995 this triggered a kind of Renaissance with lasting consequences. Actually this new philosophical impulse experienced a parallel renewal in the fields of theoretical computer science, computational linguistics, artificial intelligence and the formal semantics of programming languages triggered by the work of Johan van Benthem and collaborators in Amsterdam who looked thoroughly at the interface between logic and games. New results in linear logic by J-Y. Girard in the interfaces between mathematical game theory and logic on one hand and argumentation theory and logic on the other hand resulted in the work of many others, including S. Abramsky, J. van Benthem, A. Blass, D. Gabbay, M. Hyland, W. Hodges, R. Jagadeesan, G. Japaridze, E. Krabbe, L. Ong, H. Prakken, G. Sandu D. Walton, and J. Woods who placed game semantics at the center of a new concept in logic in which logic is understood as a dynamic instrument of inference.
If you don't believe me, see for yourself: https://en.wikipedia.org/wiki/Game_semantics I have not edited Wikipedia to have it read this way for the purpose of proving a point: https://en.wikipedia.org/w/index.php...action=history I would prove I'm not Japaridze if I could, but I can't think of a way to do that right now other than by inviting him to join us here, which I'm not crazy enough to try. Paranoia about my motives is very off-putting to me, so I'm not going to discuss this subject in the future. Also, I may not respond immediately, not because I'm trying to think of a way to maliciously turn the subject towards game semantics, but because I'm going through preop for a medical procedure tomorrow.)

Last edited by zambod; June 8th, 2017 at 01:00 PM.
zambod is offline  
June 8th, 2017, 01:01 PM   #15
Senior Member
 
Joined: Aug 2012

Posts: 1,510
Thanks: 364

Quote:
Originally Posted by zambod View Post
I'm going through preop for a medical procedure tomorrow.)
Best of luck with your medical procedure.

Honestly I can't really comment any more regarding theoretical CS. I pretty much told you everything I know.
Thanks from zambod
Maschke is offline  
June 8th, 2017, 02:19 PM   #16
Senior Member
 
Joined: Aug 2012

Posts: 1,510
Thanks: 364

Quote:
Originally Posted by zambod View Post
I would prove I'm not Japaridze if I could, but I can't think of a way to do that right now other than by inviting him to join us here, which I'm not crazy enough to try. Paranoia about my motives is very off-putting to me, so I'm not going to discuss this subject in the future.
ps -- I asked several posts ago if you were the author of the paper. You said no. I accepted that. I don't know why you think I didn't. I asked a simple question, you answered it.

The Wiki page on CoL does look like self promotion by the author of the paper or one of his friends. It's obvious from the content. The comments on the associated Talk page show that others (not just me) have the same impression.

Again, best of luck with your medical procedure. I've had a few myself and the doctors are amazing these days.

Last edited by Maschke; June 8th, 2017 at 02:28 PM.
Maschke is offline  
Reply

  My Math Forum > Math Forums > Math

Tags
foundations, questions



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Need recommendations for a good foundations of mathematics b vindy Math Books 1 February 22nd, 2014 08:07 AM
Calculus Foundations (Leibniz and Berkeley) bt359 Calculus 1 November 15th, 2013 11:39 AM
Foundations of Geometry carl1234 Math Books 3 February 21st, 2010 01:44 PM
Foundations of Mathematics CRGreathouse Applied Math 10 July 26th, 2008 08:26 PM





Copyright © 2017 My Math Forum. All rights reserved.