Recent content by SSequence

Here is the answer to your specific question. With each partial computable function ##f:\mathbb{N} \rightarrow \{0,1\}## we first need a way to associate with it a real number (in decimal form) in the interval [0,1]. Suppose we denote the set ##A## as the set of all partial computable functions...

Let me specifically focus on functions from ##\mathbb{N}## to ##\{0,1\}## [instead of computable number] and different reditions of a method similar to what you described in the OP. I will describe the various conclusions we can draw from them. (1) Firstly, we have an (easily understandable)...

I think this multiple use of ##+## is very common. Now I don't know whether the newer texts use this or not, but at least in the older texts that was the case. For example, if the alphabet is ##\Sigma=\{a,b\}##, an expression like ##(a+b).a^{+}## would mean the following language...

I don't know, but I am having difficulty seeing how ##(R+SU^*T)SU^*## can really be a correct expression? I mean consider any string accepted by the automaton you posted such that it contains at least 2 or more ##R##'s. For example, consider the string ##RRS##. It is accepted by the automaton...

Yeah well if we just want to look at it in a very high level way, it seems that "perhaps" it can be summarized into what we can call "part vs. whole" or "internal vs. external" issue. What we have is a predicate ##F(i)## which can be expressed as a ##PA## formula. So, we will have ##F(0)##...

So having spent some time (looking at various resources too), this is that partial understanding of it that I can manage. Note that this is just my (incomplete) understanding/interpretation of it (as it currently stands) and I don't know to what extent it does or doesn't represent the actual...

I was looking at stevendaryl's informative posts related to this from few years back. It occurs to me that there is at least one way to think of associating a collections of sets [each set being subset of ##\mathbb{N}##] with ##PA##. One way is to look at all predicates of form ##P(x)## where...

I don't know anything about second-order, so I can't comment much on points related to that. However, it is worth mentioning that "second-order-arithmetic" can also often refer to a first order theory (often written as ##\mathrm{Z}_2##).

I don't know, for example, how closely the version of "untyped" lambda calculus [as, for example, described in notes linked in post#8] corresponds to the original one. Nevertheless, years ago I remember reading an interview. I don't remember it exactly, but this is what I re-call. Kleene...

I think I would add one point here. It seems useful to describe it since it has not been mentioned directly in the thread yet. Consider two circles ##C_1## and ##C_2## of radii ##r_1## and ##r_2## with their centers at points ##(x_1,y_1)## and ##(x_2,y_2)## respectively. Then the following...

Yeah you are right about that. This is the natural precise definition when one is using semi-formal prose as commonly used in math texts. Post#10 also mentioned this definition. I was just thinking about extra restriction of not using a sequence such as ##\{n_k\}## directly and then only relying...

I was thinking about the logical definition of sub-sequence using quantification on ##\mathbb{N}## alone. We are given sequences ##\{a_m\}## and ##\{b_n\}## and we want to determine whether the sequence ##\{b_n\}## is a sub-sequence of ##\{a_m\}## or not. Yesterday I was thinking about it and...

Not sure I should bump the thread for a small point. But I think I kind of get how the symbol ##:## seems pretty reasonable for use in logical statements (or representing predicates etc.). Though for longer expressions, personally I think it might be easier to use brackets (at least for me)...

I would write: ##\forall x \in \mathbb{Z} \, \exists y \in \mathbb{Z} \,\, [ x>y ] ## ##\forall x \in \mathbb{Z} \, \exists y \in \mathbb{Z} \,\, ( x>y ) ## It is also OK to write something like: ##\forall x \in \mathbb{Z} \, [\, \exists y \in \mathbb{Z} \,\, ( x>y ) ] ## ##\forall x \in...

Here are some of my thoughts on this topic. I have to say that I am not satisfied about my understanding of this (that is, looking at elementary equations from perspective of logic). There are number of things that can be confusing for me in this. Honestly, this is one of the reasons (amongst...