The 2024 Developer Survey results are live! See the results

# Questions tagged [function]

The tag has no usage guidance.

21 questions
Filter by
Sorted by
Tagged with
1 vote
111 views

### 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 ...
44 views

### 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 ...
• 2,040
60 views

### 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, ...
• 101
290 views

### 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 ...
• 1,214
379 views

### 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 ...
92 views

### 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 ...
144 views

### 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 ...
• 505
77 views

322 views

### 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 ...
678 views

### 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 ...
• 5,335
625 views

### 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 ...
• 505
229 views

### 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 ...
132 views

• 32.1k