All Questions

Filter by
Sorted by
Tagged with
1
vote
1answer
24 views

Does Types and Programming Languages use a recursive equation to define a recursive type or its generator?

In Types and Programming Languages by Pierce et al: The recursive equation specifying the type of lists of numbers is similar to the equation specifying the recursive factorial function on page 52: ...
-1
votes
1answer
105 views

Is the infinite program Turing-recognizable/decidable?

Imagine we have a program which does an infinite loop: while(true){loop} We run the program on a linux machine(assume the compilation is ok), then this linux ...
1
vote
2answers
110 views

Are the capabilities of programming languages the same?

Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could ...
0
votes
0answers
50 views

Mathematical resource material accompanying TAPL

I'm currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types. Prior to this chapter I found the book challenging but ...
0
votes
1answer
46 views

Would hypercomputation machines be capable of simulating/computing/programming everything?

If uncomputable numbers existed, could this hypercomputation machines compute them? Could hypercomputation compute all types of uncomputable things? Even truly inconsistent things? Even things that ...
0
votes
1answer
43 views

Basic control statements for Turing equivalence? [duplicate]

Apologies ahead of time, I don't fully understand what I'm asking... But, is it possible to program using only 'while loops' and still be Turing equivalent? Or more generally, can I do everything ...
26
votes
7answers
7k views

Are all turing complete languages interchangeable

Note, while I know how to program, I'm quite a beginner at CS theory. According to this answer Turing completeness is an abstract concept of computability. If a language is Turing complete, then ...
1
vote
1answer
112 views

Metaprogramming taken to an unnecessarily high level- how can a program write not just other programs, but a programming language? [closed]

So basically, automated language-oriented programming. I've tried finding info on this concept, but have had some trouble, probably because my brain is having a bit of trouble grasping the subject ...
27
votes
6answers
8k views

Are there programs that can 'translate' source code between any two languages?

Are there programs that can 'translate' source code between any two languages (assuming the translator has access to the requisite libraries)? If there are, how do they work (techniques used, ...
5
votes
1answer
82 views

Computability of Stack Cleanliness

Brain-Flak is a minimalistic, stack-based, Turing complete, esoteric programming language. A big concern among Brain-Flak enthusiasts is a concept informally called "stack cleanliness". The basic ...
42
votes
9answers
15k views

Why are some programming languages Turing complete but lack some abilities of other languages?

I came across an odd problem when writing an interpreter that (should) hooks to external programs/functions: Functions in 'C' and 'C++' can't hook variadic functions, e.g. I can't make a function that ...
3
votes
2answers
89 views

Does every procedure have a structural equivalent?

Suppose I have a basic mathematical function like: $ f(x) = x^2 + 2$ implemented in typed pseudo-code as: int f(x) { return x*x + 2; } If we were to break ...
2
votes
1answer
55 views

Can LOOP-Programm stop when its value goes below 0?

I am wondering, if in the LOOP programing language, whether instances of the LOOP x DO P END are defined to stop in the case $x < 0$. The definition only says "...
1
vote
1answer
111 views

Calculi for a computability class

Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the ...
3
votes
1answer
89 views

Is the memory usage of total languages deterministic?

I'm interested in the memory usage of various programming languages when implemented on actual hardware. I believe that a Turing-complete programming language has, in general, unknowable memory usage ...
2
votes
0answers
104 views

What language features would I need to remove from a real programming language to make it decidable? [closed]

Let's say that I want to restrict certain features of a common programming language--for instance, C--such that the result is decidable, and thus no longer Turing-complete. What language features, at ...
21
votes
5answers
6k views

Why are functional languages Turing complete?

Perhaps my limited understanding of the subject is incorrect, but this is what I understand so far: Functional programming is based off of Lambda Calculus, formulated by Alonzo Church. Imperative ...
5
votes
4answers
1k views

Do we need recursion in programming language to solve any problem?

My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions? Assuming we are allowed to use: ...
-1
votes
1answer
191 views

Concurrent programming language being Turing-equivalent and difference between Turing-complete and equivalent

In Is concurrent language CCS or CSP turing-equivalent in language power?, the answer says that CCS or CSP is Turing-complete. But that does not seem to answer whether CCS or CCP is Turing-equivalent. ...
2
votes
1answer
251 views

Is concurrent language CCS or CSP turing-equivalent in language power?

Does the concurrent language CSP (or CCS, $pi$-calculus) model interacting machines? Is CSP (or CCS, $pi$-calculus) Turing-equivalent to other programming languages like C?
3
votes
0answers
154 views

Is there any programming system that enables reversible computations?

Better explained with examples, I need a programming system with the following characteristics: ...
2
votes
2answers
116 views

Is there a name for defining recursive functions as an infinite list of input/output pairs?

Recursive functions are usually defined by directly calling a function inside its own body. Nat = Z | S Nat double Z = Z double (S x) = S (S (double x))) What if,...
1
vote
2answers
64 views

Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype?

Let the following datatype be defined: data T = A | B T | C T T That is, B, B T, B (B T), C A A, C (B T) A and so on all are ...
0
votes
2answers
1k views

Mathematical function vs Computer program

In mathematics , an $n$-ary relation is subset of cross product on $n$ sets took under consideration. Let us take $A_1,A_2,A_3 \cdots A_n$ be the n sets. Then relation $R \subseteq A_1\times A_2\...
34
votes
2answers
6k views

What can Idris not do by giving up Turing completeness?

I know that Idris has dependent types but isn't turing complete. What can it not do by giving up Turing completeness, and is this related to having dependent types? I guess this is quite a specific ...
7
votes
1answer
1k views

How to prove the structured program theorem?

Wikipedia: The structured program theorem [...] states that [...] any algorithm can be expressed using only three control structures. They are Executing one subprogram, and then another ...
3
votes
1answer
133 views

How to eliminate for/if/while from algorithms when it's possible

Is there any way to find out how to replace for/if for elementary recursive algorithms? I know that primitive recursive functions cannot basically eliminate "for", but for elementary recursive ...
2
votes
1answer
787 views

A program that cannot be written in (simply-)typed lambda calculus but only in lambda calculus or Turing-complete language

Programmers do sometimes write a program that creates infinite loop if some particular input is passed into the program. But Simply-typed lambda calculus has to stop - so the question is, can anyone ...
27
votes
4answers
4k views

Clear, intuitive derivation of the fixed-point combinator (Y combinator)?

The fixed-point combinator FIX (aka the Y combinator) in the (untyped) lambda calculus ($\lambda$) is defined as: FIX $\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. ...
4
votes
3answers
911 views

What are the minimum requirements for a language to be considered Turing Complete? [duplicate]

Possible Duplicate: Are there minimum criteria for a programming language being Turing complete? I overheard a conversation on the topic and the conclusion that one gent came to was that in order ...
8
votes
1answer
568 views

Turing Machine-Like Formalism for The Actor Model

Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done. The Actor Model is sometimes mentioned as a more powerful computational-...
54
votes
6answers
12k views

Are there minimum criteria for a programming language being Turing complete?

Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete? From what I can tell from wikipedia, the language needs to ...
11
votes
4answers
391 views

Can you specify a programming language without implementation?

Is it theoretically possible to specify a programming language for which no implementation could exist? A programming language is a way of defining functions. An implementation means a method to ...