Questions about how specific notions have to be understood as well as conventions of notation.

learn more… | top users | synonyms

0
votes
1answer
20 views

What is difference between architecture and microarchitecture?

I am studying computer architecture. I would like to know the difference between the terms "computer architecture" and "microarchitecture".
3
votes
2answers
64 views

Does “output” always imply halting in computability?

$L = \{P : P(n)$ outputs $n^2$ for all $n \in N \}$ In questions of this nature, are we supposed to assume that "outputs" means "halts and outputs"? In modern programming languages, I can ...
4
votes
3answers
118 views

Difference between weak and strong AI

I'm trying to understand the difference between weak and strong AI. For an example, let's say we would pass the turing test - would it show strong AI or weak AI then? I don't believe that this is ...
4
votes
2answers
73 views

What is the definition of a $\Pi_1$-sentence?

What is meant when somebody says that a problem can be expressed as a $\Pi_1$-sentence? I know that for the arithmetical hierarchy, a $\Pi^0_1$-sentence is a sentence of the form $\forall n_1\forall ...
0
votes
1answer
26 views

Grammars: is there some connection between non-terminals $S$ and $S'$?

Given a grammar such as the following, does $S'$ have some special meaning or does it just denote another non-terminal like $B$, $A$, $P$, $Q$ etc.? $$\begin{align*} S &\to aBS'\\ B ...
1
vote
0answers
36 views

What is regular about regular languages? [duplicate]

I am new to automata theory. I am well aware of the definition of regular language in automata, that is "a language is called a regular language if some finite automaton recognizes/accepts it" [MS]. ...
0
votes
1answer
41 views

What is the difference between symbol and enumerated datatypes?

I wonder what differences and relations are between symbol and enumerated types? A symbol is a primitive datatype whose instances have a unique human-readable form an enumerated type is a ...
5
votes
2answers
175 views

What is the connection between data structures and data types?

I have read some books and wikipedia, which seem to give not completely consistent definitions and notations. I try to understand the concepts, regardless of what they are called. Here are what I have ...
3
votes
1answer
158 views

What do queues and stacks correspond to in math?

Many (and I suspect all) abstract data types in CS correspond to some math concepts, and even share the same names, for example, set, map, record/tuple, .... As abstract data types, what do queues ...
0
votes
0answers
19 views

Are fat trees dynamic or static network topologies?

Is a fat tree topology a dynamic or static network topology? Because as far as I understood a binary tree is a static topology, but we have different stages for a fat tree. Are all multistage networks ...
0
votes
1answer
49 views

Does modern type theory include specifications and implementations?

Good programming practice distinguishes between specification (at the API level) and implementation. I would have thought that this same distinction would be found in type theory. Perhaps I just don't ...
1
vote
1answer
80 views

Semantic Code Comparison

Consider two codes that do the same thing, in the same time and memory order, But they don't do it exactly the same way. Is there any Idea for a program to declare those codes as the same? For ...
0
votes
1answer
153 views

What could 'two characters are terminals' mean?

In the context of this statement, what does 'a & b are terminals' mean? Stacks and queues can be used for determining whether a particular input string is in the language or not. L = ...
2
votes
1answer
28 views

Can A still be a key if two tuples are the same

I am studying database functional dependency. It says if A can functionally determine all other attributes, it is considered to be a key. What if 2 tuples are exactly the same, can we still say A is ...
1
vote
1answer
57 views

Name for class of algorithms preserving accuracy/confidence

I am considering the following class of algorithms: The algorithm has access to some probabilistic oracle (procedure) $f$ in addition to input. The answer of procedure $f$ (we may assume it is ...
0
votes
1answer
49 views

State of variables in dynammic programming [closed]

I would like to know what a state variable is in simple words, and I need to give a lecture about it. I have chosen the Longest Common Subsequence problem I found a similar question but it has no ...
1
vote
1answer
39 views

Are neural networks dynamical systems?

Dynamical systems are those whose evolution can be described by a rule, evolves with time and is deterministic. In this context can I say that Neural networks have a rule of evolution which is the ...
1
vote
2answers
92 views

What is the term for this set

I have a set of related data/objects for which, when undergoing some algorithm, there should be only one valid match. Is there a unique term for this type of set? A common practical use case would be ...
3
votes
1answer
73 views

Conceptual question about entropy and information

Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that ...
2
votes
1answer
41 views

Is there a limit on the length of queries for the oracle?

Consider the class $L^A$ which contains all the languages that are decided by a deterministic Turing Machine that uses $O(log(n))$ space and that can make queries to an oracle that decides $A$. My ...
5
votes
1answer
48 views

What is $Prop$ in the calculus of constructions?

I'm looking at the Calculus of Constructions and its place in the Lambda Cube. If I understand correctly, each axis of the cube can be thought of as adding another operation involving types to the ...
7
votes
2answers
105 views

Combinatory interpretation of lambda calculus

According to Peter Selinger, The Lambda Calculus is Algebraic (PDF). Early in this article he says: The combinatory interpretation of the lambda calculus is known to be imperfect, because it ...
2
votes
0answers
31 views

What is a semantic cognitive map

Based on: J. P. Carvalho, "On the Semantics and the Use of Fuzzy Cognitive Maps in Social Sciences" (WCCI, 2010 -- PDF) and Richard Dagan's web page Cognitive Mapping. A cognitive map consists of ...
5
votes
1answer
61 views

Difference between hypervisor and exokernel

An hypervisor (1st type) is a software that creates and run virtual machines, managing guest's operative systems's requests to the hardware. An exokernel is an operative system kernel, that let's ...
2
votes
1answer
59 views

Use of Big-O Notation: Size of Input vs Input

It is my understanding that, when one is describing time complexity with $\mathcal{O}$, $\mathcal{\Theta}$, and $\mathcal{\Omega}$, one must be careful to provide expressions with regards to the size ...
-2
votes
1answer
38 views

Generative grammars and analytic grammars?

What are a generative grammar and an analytic grammar? How are they different from a formal grammar? Is the recursive definition of the language of a propositional calculus, a first order logic ...
0
votes
1answer
51 views

Can the definition of regular languages be simplified?

Wikipedia says The collection of regular languages over an alphabet Σ is defined recursively as follows: The empty language Ø is a regular language. For each a ∈ Σ (a belongs to Σ), ...
1
vote
1answer
74 views

recursive lambda expressions

From http://www.seas.gwu.edu/~rhyspj/spring09cs145/lab8/lab82.html The lambda operator does not bind every occurrence of its variable because "shadowing" can occur. A variable is bound by its ...
1
vote
1answer
29 views

Is random access allowed in the Bit Complexity model, or is it just expensive?

In the RAM model, you're allowed to do unbounded indirect access (pointers can be arbitrarily large and still fit in a single machine word). In the Bit Complexity model (no wiki article, sorry), ...
1
vote
3answers
86 views

Additional clarification about Simultaneous Multithreading

I was looking for comments about SMT and got several responses. The last one looks strange: Simultaneous multithreading, which can only be implemented on a multicore system, executes the ...
1
vote
3answers
94 views

What exactly is computer science? [duplicate]

I have a question that, no matter how much I think about, I do not have the answer to. The question is what exactly is computer science? The reason I am asking is that I went into college thinking ...
-1
votes
2answers
59 views

What is theory behind graphs relations? [closed]

I have been trying to understand, what is the actual meaning of 2 graphs being: Symmetric Transitive Reflexive A graph being a subgraph of another graph And ...
5
votes
1answer
69 views

Inconsistent state of a lock

I'm reading The Art of Multiprocessor programming and trying to understand their concept of inconsistent locks. Specifically, on page 37, the definition 2.8.1 of an inconsistent lock is not clear to ...
1
vote
1answer
39 views

In an M/M/1 Queue, what does exponential distribution of service time mean?

I was reading about the M/M/1 Queue and that we assume new customers arrive according to a Poisson distribution, and each customer takes an amount of time to ...
3
votes
3answers
86 views

Correct term for “string consisting of words”

In a paper I am writing I want to make distinction between (1) string consisting of any characters and (2) string consisting of a chain of words from known language, with possible delimiters. My ...
1
vote
0answers
24 views

What is the difference between “objective function”, “error function”, “criterion function” and “cost function” in the context of neural networks?

The title says it all: I have seen three functions so far, that seem to be the same / similar: error function criterion function cost function objective function I am currently working on ...
3
votes
2answers
81 views

Composition of combinators with arities greater than one

In combinatory logic, the axiom of composibility asserts that for any two combinators, $A$ and $B$, there exists a combinator $C$ that composes $A$ and $B$. That is, for all $A,B,x$ there exists a ...
1
vote
1answer
63 views

What does it mean for a function to be decidable? (homework)

Note: This is part of a homework exercise. I am asking for clarifications, not a solution! Given: Assume $g: \mathbb{N} \mapsto \mathbb{N}, g\in R$ ($R$ is the class of recursive functions) is a ...
0
votes
1answer
31 views

Name for almost random memory distribution on the heap

If I had a heap like the following: with blue blocks being occupied memory and white blocks being free memory What is the general name given to the situation illustrated, where the free and ...
3
votes
2answers
95 views

Correspondence between automata and formal grammars?

From Wikipedia Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string ...
0
votes
0answers
18 views

Clarification of the difference between join and composition of relational algebra

Hi i am statistics major student with limited mathematics knowledge. I would like to know the difference between join and composition of relations. My understanding from the reference book: Sets, ...
3
votes
2answers
90 views

Are there any CS-trees named after flora-trees?

This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real ...
1
vote
1answer
46 views

What is the difference between symbol recognition, classification and identification?

I've just wondered if there is a difference between symbol recognition, classification and identification. What would you use when you have a hand-written symbol and you want to get the LaTeX code ...
1
vote
3answers
109 views

What happens with trios, full trio, (full) semi-AFL, (full) AFL if we require closure under intersection?

Wikipedia says: A trio is a family of languages closed under e-free homomorphism, inverse homomorphism, and intersection with regular language. A full trio, also called a cone, is a trio ...
1
vote
2answers
55 views

Question about the definition of complexity class oracles

If $B$ is a complexity class, then the class $P^B$ (for example) is defined as the set of problems that can be run in polynomial time, given an oracle to every problem in $B$. That's what they told ...
0
votes
1answer
92 views

What does “finite state transduction” mean?

Wikipedia says, the regular languages are closed under arbitrary finite state transductions, like quotient K / L with a regular language. I wonder what kinds of operations "finite state ...
2
votes
1answer
72 views

Describe a TM through denotation of the transition function

I'm trying to describe a TM through denotation of the transition function. Given is a TM that recognizes the language $$ L ={\{w\#w} \mid w \in {\{0,1}\}^*\} $$ over the input alphabet: $$ ...
1
vote
1answer
65 views

Formal language inverse

How can you specify the "inverse" of a word, so: let's say a word consists of a's and b's the language is: $ww^{-1}$ the second word is the same as the first but every a is replaced by b and every b ...
1
vote
2answers
115 views

Syntax and formal grammar of a formal language

For a formal language, I wonder what differences and relations are between its syntax and its formal grammar. A formal grammar is a set of formation rules that describe how to generate the strings ...
6
votes
5answers
150 views

What does apostrophe-like symbol in the superscript mean?

It's hard to look up the meaning of a symbol if you don't know what it is called in the context that it is written. That apostrophe-type symbol in the sequence notation - what is that?