Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [function]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer

Turing 1936 Skeleton Tables Procedure

I am reading Turing 1936 to learn about the halting problem from its origin. However, I encountered a roadblock upon reaching section four, in which Turing demonstrates that his m-configuration tables ...
Missingno's user avatar
2 votes
0 answers

Effective algorithms for finite lattices of (higher-order) monotonous functions?

I am looking for references on effective algorithms on finite lattices or posets, and in particular on lattices of monotonous functions between two lattices, with higher-order structure -- monotonous ...
gasche's user avatar
  • 2,040
0 votes
0 answers

Input-Output Machines

From what I know, there is a vast literature on language recognizers in computer science. Language recognizers are machines (e.g., Finite State Automata, Pushdown Automata, Turing Machines, ...) that, ...
Sam's user avatar
  • 101
11 votes
1 answer

Existence of injective length-preserving rational function to a smaller alphabet

(This is a simpler rephrasing of an earlier question I have since deleted.) Definitions For this question, a finite-state transducer is like a standard NFA, except at each transition, the transducer ...
Jake's user avatar
  • 1,214
0 votes
1 answer

What is a "Covering Function"?

In Idris2, I will sometimes get an error telling me that a function "is not covering", which is apparently distinct from it not being total (and I do understand what a total function is). I ...
MCLooyverse's user avatar
-1 votes
1 answer

Is function composition associative in non-pure programming languages?

We know that function composition is associative in theoretical programming languages such as STλC, and pure functional programming languages such as Haskell. Is the same true for languages where ...
Michele De Pascalis's user avatar
0 votes
1 answer

What is a known sequence for which being constant is not provable?

My question concerns the property of being constant for computable functions ${\mathbb N}\to \{0,1\}$, within any common framework $T$ strong enough to include Heyting arithmetic (and of course not ...
Nikolaj-K's user avatar
  • 505
-1 votes
1 answer

Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$

Define the multi-dimension concave function $f(x): \mathbb{R}^n_+ \rightarrow \mathbb{R}_+$ where $x \in \mathbb{R}^n_+$, here I use $\mathbb{R}_+$ to represent the range $[0, \infty)$ and we let $f(\...
user avatar
3 votes
1 answer

Examples of nontrivial non-discriminatory functions

I am reading Cybenko's "Approximation by Superpositions of a Sigmoidal Function". The paper defines a discriminatory function as: $\sigma$ is discriminatory if for a measure $\mu$, \begin{align} \int ...
LYH's user avatar
  • 63
7 votes
0 answers

Universal approximation theorem of second order

The universal approximation theorem ( informally states that up to several conditions, any function can be approximated by a shallow ...
tomerg's user avatar
  • 181
7 votes
0 answers

A class of functions on a lattice that are easy to optimize

Let $({\cal P}(X),\subseteq)$ be the subset lattice for a finite set $X$. Consider a function $f:{\cal P}(X)\to \mathbb{R}$ with the following property: Given any element $I_0\in {\cal P}(X)$, there ...
sirolf's user avatar
  • 201
7 votes
1 answer

Composition of $FP$ and $\#P$ functions

Let $f_i \in FP$ and $g_i \in \#P$ for $i \in \mathbb{N}$. It is known that: $f_1(f_2(x)) \in FP$ and that $g_1(f_1(x)) \in \#P$. Is it known whether or not $f_1(g_1(x)) \in \#P$ or maybe $f_1(g_1(...
Abraham Moshowitz's user avatar
3 votes
1 answer

Is there any good literature on the computational complexity of function problems?

There are some cstheory questions that touches function-problems. Like this: Complexity class corresponding to sorting So here is the question: Is there good literature about the computational ...
Landarzar's user avatar
15 votes
1 answer

Why was Schönfinkel's work on eliminating "bound variables" in logic so crucial?

AFAIK, The first evidence of using higher order functions goes back to Schönfinkel's 1924 paper: "On the Building Blocks of Mathematical Logic" - where he allowed one to pass functions as ...
PhD's user avatar
  • 5,335
3 votes
2 answers

Constructing terms of function types out of the empty type

If a function $f$ is understood as its graph, i.e. a set of pairs $\langle x,y\rangle$ where $x$ is input and $y$ is output, then the empty set $\emptyset$ is a valid function, and for any set $A$, we ...
Nikolaj-K's user avatar
  • 505
-1 votes
1 answer

Newbie question: Meta-functions?

Consider a function F that takes a function and produces a function based on structure of the input function. As an example consider F that takes all functions having at least two conditionals and ...
Andrew Butenko's user avatar
8 votes
0 answers

Can polynomial-sized circuits use garbage?

This is a non-uniform (and simplified) version of my previous question about Cook reductions. Let $R\subseteq \{0,1\}^*\times\{0,1\}$. A function $r\colon \{0,1\}^*\to\{0,1\}$ solves $R$ if $(x,r(x))\...
Colin McQuillan's user avatar
3 votes
1 answer

Cook reduction for search problems, by universal property?

A search problem is a relation $R\subseteq \Sigma^*\times\Sigma^*$. A function $f\colon \Sigma^*\to\Sigma^*$ solves $R$ if $(x,f(x))\in R$ for all $x\in\Sigma^*$. Define a search problem to be ...
Colin McQuillan's user avatar
32 votes
1 answer

Programming languages with canonical functions

Are there any (functional?) programming languages where all functions have a canonical form? That is, any two functions that return the same values for all set of input is represented in the same way, ...
math4tots's user avatar
  • 423
6 votes
1 answer

Combining (block)-sensitivity and Lipschitz conditions?

If we're given a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, we can define its sensitivity as follows. The sensitivity $s(f, w)$ with respect to input $w$ is the number of ways of flipping a ...
Suresh Venkat's user avatar
18 votes
1 answer

Universal Function approximation

It is known via the universal approximation theorem that a neural network with even a single hidden layer and an arbitrary activation function can approximate any continuous function. What other ...
Opt's user avatar
  • 1,311