Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
3
votes
1answer
317 views

More complex integers

In connection to this question: Expected values of Kolmogorov complexity in a random sample Let $n$ be number of bits. Let $A = \{0,1,2,\dots,2^{n}-1\}$ be indexed by the $n$-bits. Let $ \delta > ...
4
votes
2answers
257 views

Mathematical explanation of recursion and lambda (referenced in The Little Schemer)

In the preface of Friedman and Felleisen's book The Little Schemer it states: We could, for example, describe the entire technical content of this book in less than a page of mathematics, but a ...
3
votes
1answer
2k views

Definition of a prefix-free Turing machine

A prefix-free function is one whose domain is prefix-free. Similarly, a prefix-free (Turing) machine is one whose domain is prefix-free. It is usual to consider such a machine as being self-...
14
votes
2answers
3k views

What is the “nearest” problem to the Collatz conjecture that has been successfully resolved?

I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ripe for such problems"). ...
1
vote
1answer
107 views

Is predicting (in the limit) computable sequences as hard as a dominating function?

Define a "predicting oracle" to be an oracle that does as described in this question. default (weak) version: Is it the case that, for every predicting oracle $O$, there exists an oracle machine $M$...
2
votes
2answers
362 views

Difference between Stencil -structures and Cellular Automata Category-theoretically?

Definitions Stencil = "For a given point, a stencil is a pre-determined set of nearest neighbors (possibly including itself)." (source) Wikipedia's definition (source) = It looks ...
2
votes
2answers
2k views

Is a turing machine with random number generator more powerful?

Let's extend the Turing machine so that it can read from a stream of random number generators (in addition to an infinite tape to read and write). Certainly the TM with randomness can do whatever a ...
17
votes
2answers
2k views

Decidability of fractal maze

A fractal maze is a maze which contains copies of itself. Eg, the following one by Mark J. P. Wolf from this article: Begin at the MINUS and make your way to the PLUS. When you enter a smaller copy ...
4
votes
1answer
1k views

Initial conditions for universal Rule 110

In A New Kind of Science, Wolfram proves that the Rule 110 cellular automaton can emulate a cyclic tag system, and is therefore a universal computer. I was wondering what specific initial conditions ...
2
votes
0answers
186 views

Particle collisions for universal computation

Proof of universality of Game of Life is straightforward (CAFAQ): (two annihilating glider streams with gaps (ie. 0s) are colliding, one is "data" and the second is all glider filled, ie.: 111111.....
0
votes
2answers
514 views

largest language class for which inclusion is decidable

am wondering what is the largest language class that is known for which set inclusion is decidable, ie a class such that if $A, B$ are in that class then $A \subset B$ is decidable. am also ...
29
votes
1answer
2k views

Halting problem, uncomputable sets: common mathematical proof?

It is known that with a countable set of algorithms (characterised by a Gödel number), we cannot compute (build a binary algorithm which checks belonging) all subsets of N. A proof could be ...
29
votes
1answer
930 views

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, ...
9
votes
3answers
841 views

Decidability of transcendental numbers

I have a question, whose answer is probably well known, but I can't seem to find anything meaningful after a bit of searching, so I would appreciate some help. My question is whether it is known that ...
7
votes
2answers
363 views

Which model of computation to simulate to prove universality?

I am starting out in theoretical computer science. I have a model of computation based on observations of auto-associative memory in the brain. I believe (with little evidence) that I can do ...
3
votes
1answer
299 views

Abstract definition of universal computation

There are many universal computation systems. Turing machines, tag systems, rewrite systems, cellular automata to name just a few. The universality of a system is proved via reduction from a known ...
4
votes
0answers
375 views

Are there connections between Turing machines and symbolic dynamic systems?

On a course, when shift systems were being introduced, the lector said that "if the shift of symbols sequence reminds you Turing machine, then it is a very correct association": $\sigma(\ldots, x_{-1}...
4
votes
2answers
932 views

Transition Diagram of a Universal Turing Machine

I have searched the web for the transition diagram of a universal Turing machine without luck. Is anyone aware of such a diagram? I need this as a reference, so preferably a book or a published ...
31
votes
6answers
5k views

What's the simplest noncontroversial 2-state universal Turing machine?

I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness. So far I've created a game state ...
1
vote
1answer
287 views

Concerning decidability of a problem on real numbers [closed]

This question is an outgrowth of a certain maths problem I've been thinking about. Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer ...
12
votes
5answers
1k views

Are there decidable problems for which for no algorithm we can give time bounds?

Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance? I arrived at this question because I was ...
19
votes
3answers
1k views

Is the concept of the Turing Machine derived from automata?

I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"? I didn't know the answer of course, but I'...
4
votes
4answers
671 views

Examples of reversible computations

Irreversible computations can be intuitive. For example, it is easy to understand roles of AND, OR, NOT gates and design a system without any intermediate, compilable layer. The gates can be directly ...
0
votes
1answer
210 views

Halting on a (possibly one-way) write-once tape

Consider Turing machines (with the Busy Beaver "design specifications") that must write a 1 whenever they read a 1 (i.e., "write once"). ${}$1. $\:$ Is the halting problem decidable for these ...
-1
votes
1answer
2k views

Decidability of the halting problem on finite computers [closed]

I've seen two competing and contrary arguments for this problem. One states that real computers are linear-bounded automata, and therefore the halting problem is decidable. The other states that ...
22
votes
1answer
1k views

Class of functions computable by Coq

Since it does not allow nonterminating computation, Coq is necessarily not Turing-complete. What is the class of functions that Coq can compute? (is there an interesting characterization thereof?)
2
votes
1answer
487 views

Three questions about finite state machines

Suppose a finite state machine, FSM, has a fixed set of states $S$ and input/output channels $C$, and is uniquely specified by the fixed map $m : S\times D \to S\times D\cup {0}$. If a state $(c_i,s_j)...
8
votes
2answers
335 views

Using negative results to prove positive results in computability theory

Many results in cryptography depend on impossibility results/conjectures in complexity theory. For example, public-key cryptography using RSA is believed to be possible because of the conjecture about ...
4
votes
1answer
387 views

Is every busy beaver strictly monotonic asymptotically?

To be specific, let me first define the busy beaver function BB(n)= maximum number of 1's that can be printed on the tape (i.e., the maximum score) by a standard n-state, 2-symbol (0 and 1) Turing ...
18
votes
3answers
2k views

Why has hypercomputation research died down?

I see a lot of research on hypercomputation in the 1990's, but in more recent years there seems to be little work on the topic. Is it true that research in this area has died down? If so, what could ...
2
votes
1answer
257 views

FSMs with finite memory

Consider an FSM and a finite set of variables. The FSM has the special property that each state contains a set of commands, with each command taking the form of "variable = expr(variable, ...)" e.g., ...
12
votes
2answers
235 views

Reducing threshold questions to finiteness questions

It is usually simpler to reason about calculus where the limitation is finiteness of computation rather than a threshold like "computable in polynomial amount of time". In formal languages theory for ...
6
votes
1answer
376 views

Term that can distinguish beta-equivalent normal forms in the untyped lambda calculus

I'm trying to work through two (non-assessed) class-work questions and am stuck on a question that seems similar to one I could do. The first question was to prove that there does not exist a $\...
8
votes
2answers
273 views

Is there any work done on developing difference-calculus of Turing Machines (or simpler Formal Languages)

I am attempting to develop some notions of a difference-calculus between a notional Ideal Turing Machine conceived by a developer (e.g. whatever is intended by a software developer), call it $M_I$, ...
-2
votes
1answer
732 views

Is there any proof that a network made of Turing machines can't solve the halting problem? [closed]

My question points to the fact that Turing machines are isolated by definition. But what if they can send and receive information from/to other Turing machines? What if they can be "interrupted" at ...
5
votes
0answers
351 views

Does $\Sigma(n+1)-\Sigma(n)$ eventually dominate every computable function?

Let $\Sigma$ be Radó's Busy Beaver function, and define $\Delta(n) \ = \ \Sigma(n+1) - \Sigma(n)$ for all $n \in \mathbb{N}$. Question: Does the function $\Delta$ eventually dominate every ...
-4
votes
2answers
651 views

Is halting that hard? [Yes] [closed]

I want to make a modification to the halting problem. The output now has two possibilities: This program halts and it does not have the crossing structure (defined below); This program does not halt ...
20
votes
3answers
2k views

If an abstract machine can simulate itself, does that make it Turing complete?

For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e....
16
votes
2answers
2k views

Can chess simulate a Universal Turing Machine?

I am looking to get a definite answer to title question. Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white ...
5
votes
3answers
350 views

Hilbert's Tenth Problem and nonrecursive Diophantine sets

In her paper Defining Integers, Alexandra Shlapentokh presents the following as an immediate corollary of the undecidability of Hilbert's Tenth Problem --- that is, the language $\{p : p$ is a ...
10
votes
3answers
674 views

Computational hardness of “real” computer programs

I have often heard it said that you cannot write a program to catch bugs in a web browser, or word-processor, or operating system, because of Rice's Theorem: any semantical property for a Turing-...
7
votes
2answers
296 views

Simple model of computation with homoiconicity

Is there a simple model of computation with homoiconicity? It would also be nice if, like beta reduction in lambda calculus, every step in execution yields a new valid program. Besides the lack of ...
22
votes
3answers
831 views

Complexity of Tensor Rank over an Infinite Field

A tensor is a generalization of vectors and matrices to higher dimensions and the rank of a tensor also generalizes the rank of a matrix. Namely, the rank of a tensor $T$ is the minimum number of rank ...
11
votes
2answers
1k views

Decidability of equality of CFL's

Following problem is decidable: Given a context-free grammar $G$, is $L(G) = \varnothing$? Following problem is undecidable: Given a context-free grammar $G$, is $L(G) = A^{\ast}$? Is there a ...
14
votes
1answer
253 views

Do there exist groups with word problems in arbitrary P-degrees?

It has been known for a long time that, given any r.e. Turing degree, there is a finitely presented group whose word problem is in that degree. My question is whether the same thing is true for ...
6
votes
0answers
488 views

Prove Post Correspondence Problem Non-Recursive Without Reduction

Given a set of pairs of words $P = \{(\alpha_1, \beta_1), \dots, (\alpha_n, \beta_n)\} \subseteq \Sigma^*\times\Sigma^*$, the Post Correspondence Problem (PCP) is to decide wether or not there are ...
12
votes
2answers
402 views

Kolmogorov complexity with weak description languages

We can think of Kolmogorov complexity of a string $x$ as the length of the shortest program $P$ and input $y$ such that $x = P(y)$. Usually these programs are drawn from some Turing-complete set (like ...
18
votes
4answers
807 views

Can testing show the absence of bugs?

$(n + 1)$ points are required to uniquely determine a polynomial of degree $n$; for instance, two points in a plane determine exactly one line. How many points are required to uniquely determine a ...
2
votes
2answers
154 views

how to formalize the class(?) of computational models and their equivalence

Introductory books to theoretical computer science usually introduce a the Turing machine and some of its variants, as well as the Random Access machine as computational models. Sometimes more ...
4
votes
1answer
894 views

Why have computer scientists chosen recursor instead of iterator in primitive recursion?

I wonder why computer scientist have chosen recursor instead of iterator (or tail recursor if you like) in primitive recursion, given that function defined in terms of iteration behaves more ...