Questions tagged [computability]
Computability theory a.k.a. recursion theory.
367
questions
0
votes
0answers
32 views
Is having a particular form equivalent to being computable for functions on Church numerals?
In SKI-combinator calculus, consider the following function which reduces an expression (involving SKI and variables) to a canonical form:
...
3
votes
0answers
55 views
Expressive power of lambda-calculus with restricted application
Consider a syntactic restriction of the (untyped) $\lambda$-calculus in which an application cannot have another application as an immediate subterm. More precisely, restricted terms ($R,S,...$) and ...
4
votes
1answer
214 views
Why are some classes (ALL, ELEMENTARY, R, etc) badly behaved as oracles?
Some classes, such as ALL, ELEMENTARY, and R, are very badly behaved when used as oracles. For instance, all three of these classes trivially collapse P and EXP, even though (by the Time Hierarchy ...
3
votes
0answers
109 views
Detailed proof of Theorem 2.1 in Papadimitrou book (Multitape TM to SingleTape TM)
I want to know if anybody knows a detailed proof of Theorem 2.1 of Papadimitrou's book Computational Complexity. The theorem states "Given any $k$-string Turing machine $M$ operating within time $...
7
votes
0answers
115 views
Halting problem for finitary PCF
Is the halting problem decidable for finitary PCF? By "halting problem" I mean the problem of deciding whether a closed PCF term evaluates to bottom under the denotational semantics of PCF. ...
-1
votes
1answer
66 views
Is there a fundamental link between Nash's equilibrium and Turing's halting problem?
Since Nash equilibrium exists, is there a computational analogue of this equilibrium point? I am trying to approach Nash equilibrium from computational point of view to see if the equilibrium point ...
0
votes
1answer
128 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 ...
7
votes
1answer
197 views
What is the complexity class of higher-order primitive recursion?
Short and sweet: The complexity class of primitive recursive functions (WP) is PR (WP, Zoo). What's the complexity class of higher-order primitive recursion (WP)?
The motivating context is simply that ...
2
votes
1answer
170 views
A variant of two-counter machine
I would like to show that the halting problem for some variant of two counter machine (Minsky machine) is undecidable:
instead of "if c=0 goto i else goto j", there are "if c>d goto ...
5
votes
1answer
305 views
Is coRE closed under concatenation?
I know that RE is closed under union, intersection, and concatenation (but not complement). It is likewise easy to show that coRE is closed under union and intersection (but not complement). What ...
0
votes
0answers
134 views
Is BigInteger-based Brainfuck Turing Complete?
All of the proofs of Turing-Completeness I've found for Brainfuck rely on its cells being fixed-width integers that wrap around upon over/underflow. The "parent language" P'' on which ...
2
votes
0answers
103 views
Halting behavior of a randomly selected Turing machine?
Let $TM(k,2)$ be the set of Turing machines with $k$-states and $2$ symbols. Let $h(k)$ be the number of machines in $TM(k,2)$ that halt when run on the blank input.
Is
$\lim_{k \to \infty} \frac{h(k)...
3
votes
0answers
55 views
Is relativization statement-dependent or proof-dependent?
I'm relearning some computability theory, and have encountered the idea of relativization of results to arbitrary subsets of $\omega$ and the subtlety of figuring out what the correct relativized ...
-2
votes
1answer
123 views
Where, if any, is there currently any research being done on the subject of ternary computers? [closed]
I had the experience several years ago of working with a team that had developed a ternary computing system. It ran out of funding and was abandoned but I felt it was ahead of its time. Currently, ...
3
votes
1answer
265 views
Proof and computational complexity
I couldn't find documents elaborating on this: if the Curry Howard correspondence is to be interpreted as establishing a strong relation between proofs and programs, should there not be a strong ...
1
vote
0answers
45 views
A proved computationally-irreductible function
In arXiv:1111.4121 and arXiv:1304.5247, Hervé Zwirn and Jean-Paul Delahaye propose a formal definition of computational irreducibility. Is there a (possibly artificial) function that can be proved to ...
0
votes
0answers
222 views
What is the difference between a model of computation and a programming language?
https://en.wikipedia.org/wiki/Model_of_computation includes sequential models, functional models and concurrency models.
Sequential models include finite state machine, Turing machines, random access ...
4
votes
1answer
173 views
Is this variant of bitwise cyclic tag Turing-complete?
Cross-posted to MathOverflow.
CT is an extremely minimalist programming language that can simulate arbitrary tag systems, and is therefore Turing-complete. A program consists simply of a string of 3 ...
3
votes
1answer
115 views
What is the meaning of 'uniform' in Blum's paper "On the Size of Machines"
In Blum's "On the Size of Machines" he uses the word 'uniform' in several places.
For instance, in Theorem 1, he writes
Let $f$ be any recursive function. Then there exists $i,j\in \mathbb{...
15
votes
1answer
659 views
Computability and continuity
Say $L_1$ and $L_2$ are computable languages. Let $f$ be a function $L_1 \rightarrow L_2$. Let $C$ be the statement, "if $l \subseteq L_2$ and $l$ is a computable language, the preimage $f^{-1}(...
1
vote
0answers
107 views
Functional abbreviation for Inst expression in Turing's 1936 paper
In Turing's 1936 paper "On Computable Numbers",
For a Turing Machine $M$, $Inst(q_i S_j S_k L q_l ) $ means that if $M$ scans symbol $S_j $ under $m-configuration$ $q_i$, then the symbol ...
-1
votes
1answer
114 views
Are all computable functions monoidal from a category theory POV? [closed]
I have been studying some category theory only to understand the "why" behind the various categorical constructs we use ("borrow") in the world of functional programming.
One of ...
11
votes
1answer
227 views
Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?
I hope that mathematical logic / recursion theory type questions are welcome here. I am sorry this question is so long and technical, but I believe that if you read it you will find that it is well-...
1
vote
1answer
187 views
How come Wikipedia says that Random Turing Machines can provide uncomputable output?
Wikipedia article mentioned : Hypercomputation
The third paragraph starts off with:
Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses ...
1
vote
1answer
146 views
What kind of computational model is the brain? [duplicate]
I was wondering what kind of computational model is the human brain (as it seems superior to a Turing machine).
Another thing that should be a separate question, What would be a perfect computer model ...
12
votes
2answers
447 views
Complexity relative to the graph of the Busy-Beaver function
This question is inspired by the comments made on this other question that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree $\mathbf{0}$. (...
5
votes
0answers
218 views
Has there been any development of complexity theory for other Turing degrees than 0?
(I'm not sure if this question is better suited for MathOverflow or here. I'll try here first, and move over to MO later if it appears to be more appropriate.)
Complexity theory can be very broadly ...
1
vote
0answers
74 views
Given a program specification, S, what can be said about the size and efficiency of programs that exactly satsify S, with respect to the size of S?
Suppose we are given a program specification, $S$, and we want to reason about programs $P$ that satisfy $S$. One might like to think that if the specification is 'simple', the the program should be '...
4
votes
0answers
100 views
Logic of learning
Does Robust logic (Leslie Valiant), Default logic (Raymond Reiter) and Circumscription logic (John McCarthy) have any relation?
I was Mathematician and Computer Science (dual degree undergraduate) ...
-2
votes
1answer
99 views
Definition of Omega Jump [closed]
In the book Computability theory (Rebecca Weber) I stumbled about Exercise 7.1.24 with the definition of the omega jump.
The book says:
The omega jump of $A$, $A^{(\omega)}$ is the join of all $A^{(n)}...
1
vote
0answers
34 views
Non Turing-Complete Models, Conditional-Complete function?
I know well the distinction between the class of Partial Recursive Functions, and $\mu$-Recursive, i.e. the latter is Turing Complete and the former is equivalent to the LOOP-Program model of ...
-3
votes
1answer
109 views
Is this a good definition of computability? [closed]
I still haven't found a good definition of computability. All the definitions are either too vague, or they delegate the definition to another loaded term like "anything that uses math to solve a ...
1
vote
1answer
165 views
Extended Church's thesis and internal parametricity
I am wondering if there is any known relationship between these 2 concepts in intensional MLTT as formulated here.
Does $Internal\ parametricity \implies ECT$ hold?
For forumlation of ECT see https://...
0
votes
2answers
197 views
Is the decidability of a language decidable? [closed]
Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language?
Comments + answer say trivially the answer is yes; however, I'm wondering here would ...
-1
votes
2answers
199 views
Turing meta-oracle
Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...
1
vote
0answers
48 views
Is there an alternative technique to define computable functions other than their definition on natural numbers? [closed]
I am not completely sure that why computable functions is defined as a subset of all functions from/to Natural Numbers, but as far as I know, computation comes from real (physical) world so ...
5
votes
0answers
92 views
Are there languages require many variables to achieve $\Sigma_n^0$ completeness?
The proof of Post's Theorem that I am familiar with assumes you have access to as many variables as you wish in your language. Matiyasevich's Theorem by contrast gives a $\Sigma_n^0$-complete formula ...
-1
votes
1answer
129 views
Gödel-Numbering of the Context-Sensitive Languages
I would like to have a Gödel-numbering of the context-sensitive languages. Because there is no obvious syntactic distinction between LBAs and TMs, I cannot number the former in an immediate way. So I ...
7
votes
1answer
325 views
Uniform mortality problem for Turing Machines
Consider the following generalisation of the mortality problem for Turing Machines.
Given a Turing Machine $M$. Is there a bound $k_M$ such that starting
from any configuration $c$ machine $M$ ...
3
votes
2answers
198 views
Compactness of domino tilings
I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted. This sounds like a compactness property, ...
2
votes
0answers
88 views
how is time complexity defined in computational learning theory
In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$.
Now ...
0
votes
1answer
183 views
Why does the Placid Platypus function grow faster than any computable function?
I came across the Placid Platypus function $PP(n)$ today, defined as the minimal number of states needed for a turing machine that prints a string of $n$ ones and halts. This function is claimed to (...
6
votes
1answer
332 views
Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?
Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity.
Background/Motivation: Coming ...
5
votes
1answer
186 views
Minimal information needed for determine some function
From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
1
vote
0answers
185 views
Solving the Halting problem for most inputs [closed]
Is it possible to solve the following version of the Halting problem : given any Turing machine and some input tape, the program should answer if this pair halts or not except possibly for one Turing ...
11
votes
0answers
201 views
Can two-tape read-only Turing machines recognize any recursive language?
Suppose that a $k$-tape read-only Turing machine receives its input on each $k$ tapes.
It cannot write on the tapes, but it can move on them in both ways, even move off from the input.
So for example, ...
6
votes
2answers
305 views
Algorithm for identifying unprovable statements
I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms?
For example: If there ...
2
votes
1answer
185 views
Is there a difference between incompleteness and unknowable? [closed]
Godel proved that there are statements that are true but not provable. Unproven conjectures such "Twin Primes" might fall into such a class, as I understand. If so, does it mean that we will never ...
6
votes
3answers
279 views
Why/when do we ever need transfinite loop variants?
I do not understand why one would ever need a transfinite loop variant.
Why do natural-number-valued variants not suffice? My simple (but perhaps too naive) argument is: if a loop $L$ terminates ...
5
votes
1answer
314 views
Is there a useful notion of being “approximately computable”
It seems that we can define a notion of being “approximately computable” where a set, $S$, is approximately computable if there is a family of computable functions $f_n(x)$ such that $$\lim_{n\to\...