All Questions
Tagged with programming-languages turing-machines
23 questions
1
vote
2
answers
72
views
In the simulation of a C-program by a Turing machine, how does a TM determine which instruction to execute?
In Arora-Barak, the authors mention a way how TMs can compute everything that can be computed by computers. The idea is that every high-level language program has an equivalent machine language ...
- 11
1
vote
4
answers
3k
views
Can we ever achieve Turing completeness?
I want to relate Turing completeness to the Halting Problem.
As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. But ...
1
vote
1
answer
172
views
kolmogorov complexity for finite Language?
In lectures my professor proved that there is no Turing machine that for every x it calculates k(x).
On the other hand, I saw a claim online that for finite language L there is a Turing machine that ...
- 61
1
vote
0
answers
227
views
How can I simulate nested WHILE loops in a theoretical programming language to show Turing completeness?
PRE-WORK-POST is a theoretical programming language with the following structure, where P,Q and R are LOOP program:
$$\text{PRE} \ P \ \text{WORK} \ Q \ \text{POST} \ R \ \text{END}$$
First $P$ is ...
- 11
5
votes
1
answer
1k
views
Explain the difference between Turing Complete and Turing Equivalence
I'm not sure if I understand the difference between Turing Complete and Turing Equivalent programming languages.
A computational system that can compute every Turing-computable
function is called ...
- 463
2
votes
0
answers
51
views
Understanding the simulate of an IF loop program through a LOOP program
We have the following operation $\text{IF} \ x_i =0 \ \text{THEN} \ P \ \text{END}$. I want to simulate this using a $\text{LOOP}$ program. Here is what I have:
$$\text{IF} \ x_i = 0 \ \text{THEN} \ P ...
- 463
2
votes
0
answers
127
views
How does one program in a tag system?
I've played with 2-tag systems a bit and read all about tag/lag systems. They're great for experimenting with computation, and obviously useful as intermediaries in various proofs.
My question is: ...
- 306
2
votes
1
answer
638
views
How to translate automatons (Turing machines) into programs of high level programming language?
Every program in high level ("industrial") programming language can be expressed as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the ...
- 1,401
5
votes
2
answers
1k
views
What can't you do without Turing-completeness?
I suppose that, since a Turing-complete language can simulate a Turing-machine, a non-Turing-complete language can't, but most programs do not have the simulation of a Turing machine as their purpose.
...
- 151
0
votes
0
answers
279
views
Converting Turing machine into the source code in industrial programming language?
Are there methods how to convert Turing machine (e.g. neural Turing machine or other rigorous Turing machine) into the source code/program that is written in some industrial programming language like ...
- 1,401
-1
votes
1
answer
662
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 ...
- 175
1
vote
1
answer
399
views
What is the relation between an algorithm and its implementation at the level of code?
Is there any isomorphism or equivalence relation? What strictly bind these two together?
- 111
2
votes
1
answer
421
views
Is the Shakespeare Programming Language Turing complete?
I was reading about tge Turing machine. I also came across with the Shakespeare programming language. After trying to understand the basics of the PL, I thought ...
- 223
1
vote
0
answers
275
views
Converting (reverse-engineering) Turing machine into program or most concise algorithm?
It is known that every program or every algorithm can be converted to Turing machine. But what about the reverse process? Is there algorithm (or research trend that considers such algorithm) to ...
- 1,401
6
votes
0
answers
83
views
Can all computational complexity results be expressed in terms of programming languages?
Computational complexity results are often explained in intuitive terms as statements about the possible efficiencies of algorithms to solve certain classes of problems.
However, on a more formal ...
- 286
2
votes
1
answer
148
views
How to implement polymorphism in a turing complete environment?
I'm currently programming in an unnamed turing complete language which has support for pointers, primitive data types, structures, closures, and garbage collection, among other things.
I'm trying to ...
- 131
5
votes
1
answer
91
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 ...
3
votes
3
answers
625
views
Formal notion of a call graph for Turing machines
To most computer programs one can assign a "call graph".
Is there a formal notion of call graphs of Turing machines?
Motivation is, that one could intuitively call a decidable language $L$ "...
user41014
4
votes
1
answer
1k
views
Official Name for the “First” Programming Language Developed by Turing?
As is widely known, Alan Turing discovered/invented the Turing Machine in his classic 1936 paper. Here he also gave how these machines are specified in terms of their machine states and instructions ...
- 141
29
votes
5
answers
10k
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 ...
- 541
5
votes
4
answers
3k
views
Can we write algorithms without conditional statements?
Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional.
Consider the factorial problem, we would typically define ...
- 475
8
votes
4
answers
4k
views
What is the exact relation between programming languages and Turing machines?
I don't know much about yacc, bison, flex or lex and please correct me if I'm wrong but a programming language is also a Turing machine and a Turing machine is defined as the tuple $(Q, \Gamma, b, \...
- 1,016
71
votes
7
answers
22k
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 ...
- 1,451