Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
2 votes
0 answers
58 views

Many-one equivalence of sets that differ finitely

[This is a duplicate of my question from Mathematics Stack Exchange: https://math.stackexchange.com/questions/4792354/many-one-equivalence-of-sets-that-differ-finitely I am posting it here since it ...
ijon's user avatar
  • 33
2 votes
2 answers
428 views

Technical limitations of Turing machines due to the input and output encoding of values

Convention: Since I will be asking about some technicalities around Turing machines, it behooves to give a precise definition: say, here, “Turing machine” will stand for a $2$-symbol $1$-tape machine ...
Gro-Tsen's user avatar
  • 619
0 votes
0 answers
40 views

Computability of Time Complexity of Recursive Sets

Is every recursive set's worst-case time complexity a total recursive function?
A. P. Pille's user avatar
0 votes
1 answer
112 views

Computational power of probabilistic automata

I am a bit confused about the proper role of probabilistic automata (PA) in the theory of computation. Informally, I can imagine they can accept more than finite automata (FA) as they, for instance, ...
Barney's user avatar
  • 109
1 vote
1 answer
55 views

Many-one degrees of some particular sets

Let $W_0, W_1, W_2,\dotsc$ be an effective numbering of r.e. sets. Consider sets $\text{Emp}=\{x\mid W_x=\emptyset\}$, $\text{Tot}=\{x\mid W_x=\mathbb{N}\}$ and $S_n=\{x\mid W_x=W_n\}$ (for some fixed ...
ijon's user avatar
  • 33
0 votes
0 answers
165 views

Decidability of the complexity of decision problems

This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
A. G's user avatar
  • 101
-7 votes
2 answers
357 views

Self Referential Undecidability Construed as Incorrect Questions

Please see my answer before you read any of this. The answer says the same thing much much more clearly PhD computer science professor Rick Hehner and I independently derived what we mutually agree ...
polcott's user avatar
  • 45
1 vote
1 answer
123 views

Primitive recursion with varying parameters

Suppose $g\colon \mathbb{N}^k \to \mathbb{N}$, $v_1,\ldots,v_r\colon \mathbb{N}^k \to \mathbb{N}^k$ and $h\colon \mathbb{N}^{k+r+1} \to \mathbb{N}$ are all primitive recursive, and define $f\colon \...
Gro-Tsen's user avatar
  • 619
1 vote
1 answer
108 views

Complexity of analytic functions and integrals

There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this: To which class do analytic elementary functions, including trigonometric ones, ...
roignoirewg's user avatar
1 vote
0 answers
55 views

Primitive recursion relative to a logical system

In various places I have read that the normally considered non-primitive recursive Ackermann function is primitive recursive in higher-order logic. It's claimed to be due to "Reynolds, 1985",...
Ilk's user avatar
  • 900
2 votes
0 answers
57 views

Complexity measures for semi-decidable problems

Is there any sensible complexity measure that makes sense to compare the "hardness" of undecidable semi-decidable problems? Time and space are of course not suitable, because they cannot be ...
Nicola Gigante's user avatar
0 votes
0 answers
63 views

What is the meaning of the additive epsilon term in the definition of a time constructible function?

There is a well-known theorem that states that a function $f$ is time constructible if and only if $f$ can be computed in time $O(f)$. But this theorem comes with some conditions: $f$ must be a ...
user70015's user avatar
9 votes
1 answer
328 views

Is P=NP relative to the halting oracle?

Consider the following variant $\mathscr{H}$ of the halting oracle: given the code $e$ for an ordinary Turing machine and an input $n$ to it, we let $\mathscr{H}(\langle e,n\rangle) = \langle 0,0\...
Gro-Tsen's user avatar
  • 619
7 votes
1 answer
293 views

Is there a well-defined notion of an “R/poly” complexity class?

This would be the complexity class of all problems that are decidable in finite time with a polynomial length advice string that can be arbitrarily hard to compute. But potentially undecidable without ...
Colonizor48's user avatar
3 votes
2 answers
121 views

What is formal definition of non-deterministic algorithm in context of primitive/general recursion?

I want to understand general method for formally defining non-deterministic algorithm. But all formal definitions I see are related to FSM/Turing-machines. What is the reference for non-deterministic ...
uhbif19's user avatar
  • 295
1 vote
2 answers
96 views

Do realizable systems always have some non-well-founded sets?

Suppose we are standing outside a realizable system which admits CZF or a similar constructive set theory. Then consider the following: LEM is not realized (e.g. this MSE answer) The traditional ...
Corbin's user avatar
  • 271
3 votes
0 answers
72 views

Generalizing Quines: Outputting an Arbitrary Function of Source Code

​​A Quine is a (non-empty) program $P$ that takes no inputs and returns its own source code $\langle P\rangle$ as the only output. For a function $f$ (with appropriate domains and range) define an $f$-...
Pooya Farshim's user avatar
4 votes
0 answers
309 views

How to prove that a language that allows infinite loops is still not Turing-complete?

CPS translations will always use pairs, either explictly or by currying. Though I can't find a reference for that, I'm assuming this is a necessary condition (I'd appreciate a reference if someone has ...
paulotorrens's user avatar
0 votes
0 answers
52 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, ...
Sam's user avatar
  • 101
4 votes
0 answers
114 views

Reference for "A Turing machine cannot be equipped with an oracle for itself"

Starting with a basic Turing machine, successive applications of the Turing jump produce successively more powerful machines, that can be indexed by any ordinal. A tempting error for students, and one ...
Alex Meiburg's user avatar
0 votes
0 answers
38 views

Computability for universal quantum turing machines

I would like to ask if anyone has any ideas about what a universal quantum turing machine (UQTM) can do as supposed to a classical universal turing machine (UTM) (i.e. quantum computer vs classical ...
Shane Gervais's user avatar
8 votes
0 answers
110 views

Does Bellantoni-Cook safe recursion (or any other implicit characterization of P) admit Kleene's second recursion theorem?

Abstractly, by a programming language that operates on binary strings I mean a set $P$ of programs along with a semantics relation $[p](x) = y$, ``the program $p$ on string $x$ halts with output $y$.&...
Siddharth's user avatar
  • 803
1 vote
1 answer
86 views

Extension of primitive recursion, that is as powerful as System-T

I know that System-T restricted to first-order types is exactly as powerful as primitive recursive functions, because I proved it in Agda. I asked myself, if there is a extension of primitive ...
ghostOfTomJoad's user avatar
-13 votes
2 answers
1k views

Can you see that the Linz Halting Problem proof contains a fatal flaw?

Applying a Simulating Halt Decider to the Linz Halting Problem Proof When a simulating halt decider correctly simulates N steps of its input it derives the exact same N steps that a pure UTM would ...
polcott's user avatar
  • 45
0 votes
0 answers
61 views

Are there parsers that can parse languages in more expressive grammars than context-free grammars?

The Earley Parser is able to parse all context-free languages. Are there parsers that can parse say languages in context-sensitive grammars? I realize ambiguous grammars are non-deterministic and ...
Vivek Joshy's user avatar
2 votes
0 answers
105 views

Gurevich's theorem on primitive recursive functions being logspace-computable

I recently came across the following result attributed to Gurevich, according to which I understood that the class of problems solvable by primitive recursive functions is precisely the class L of ...
Noel Arteche's user avatar
1 vote
0 answers
60 views

Generalization of computability to continuous for loops? [closed]

A computable function, formulated in the sense of mu recursion, can compute a for or do loop over some (possibly infinite) integer range. I was wondering if a suitable generalization exists that ...
Abhimanyu Pallavi Sudhir's user avatar
6 votes
1 answer
270 views

An analogue of Scott continuity for infinite-time-Turing-computable functions

$\newcommand{\tb}{2_{\!\bot}}\newcommand{\tbO}{\tb^{\,\omega}}$Let $2 = \{0,1\}$ and $\tb = \{0,\bot,1\}$. Scott continuity is important for defining models of lambda calculus, a formalism for ...
Jozef Mikušinec's user avatar
2 votes
0 answers
115 views

Are there more learnable but undecidable cases except the halting problem

Per request, I cross post the question here which is original from math.stackexchange In the ICML 1996 paper, On the Learnability of the Uncomputables, by Richard Lathrop, he proved that halting ...
Mountain's user avatar
  • 121
7 votes
1 answer
284 views

What are the application of Scott-Topology in theoretical computer science?

During a work I came across the Scott-Topology and I see that Scott-continuous functions show up in the study of models for lambda calculi. What I cannot understand is how this enrich the lambda-...
micrus's user avatar
  • 81
0 votes
1 answer
207 views

Understanding the construction of an uncomputable function

The following is from Arora and Barak's "Computational Complexity." I think one does not have to read the second paragraph of the proof to answer this question. Theorem 1.10 There exists a ...
zxcv's user avatar
  • 109
0 votes
0 answers
134 views

How can I switch into computability theory when I am part way through my PhD in deep learning?

I am partway through my PhD studying deep learning. I chose it just because it's useful and would yield a lot of industry opportunities. However, I am really missing my previous coursework in ...
JobHunter69's user avatar
3 votes
0 answers
79 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 ...
pbaren's user avatar
  • 653
5 votes
1 answer
238 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 ...
Demi's user avatar
  • 516
3 votes
0 answers
121 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 $...
arbolverde's user avatar
7 votes
0 answers
135 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. ...
PaR's user avatar
  • 71
0 votes
1 answer
86 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 ...
Ajax's user avatar
  • 109
0 votes
1 answer
143 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 ...
Nikolaj-K's user avatar
  • 505
8 votes
1 answer
310 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 ...
Corbin's user avatar
  • 271
2 votes
1 answer
243 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 ...
Naama Shamash Hal's user avatar
5 votes
1 answer
847 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 ...
Aryeh's user avatar
  • 10.3k
0 votes
0 answers
162 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 ...
user513093's user avatar
2 votes
0 answers
109 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)...
user101010's user avatar
3 votes
0 answers
60 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 ...
Alex Mine's user avatar
  • 139
-2 votes
1 answer
133 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, ...
tale852150's user avatar
3 votes
1 answer
297 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 ...
user1868607's user avatar
1 vote
0 answers
53 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 ...
Bob's user avatar
  • 381
0 votes
0 answers
526 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 ...
Tim's user avatar
  • 639
4 votes
1 answer
291 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 ...
user76284's user avatar
  • 652
3 votes
1 answer
154 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{...
user10108's user avatar

1
2 3 4 5
8