Linked Questions
10 questions linked to/from Is C actually Turing-complete?
4
votes
0
answers
116
views
Is every von neumann machine turing complete? [duplicate]
I understand that TM is a 'Model of Computation' which tells us about the computational power of a machine while Von Neumann Architecture is a 'System Architecture' that tells us about how the machine ...
- 41
0
votes
0
answers
99
views
Is C actually turing complete follow up [duplicate]
I am picking up from this thread for which I have no privileges to comment on:
Is C actually Turing-complete?
I was wondering if there's any progress on this and what the conclusion actually was. ...
181
votes
13
answers
66k
views
Why, really, is the Halting Problem so important?
I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine ...
- 2,543
27
votes
7
answers
8k
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 ...
- 289
11
votes
4
answers
12k
views
Does our PC work as Turing Machine?
Does our PC work as Turing Machine? The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have ...
- 273
4
votes
1
answer
3k
views
Time complexity of arithmetic operations
I want to calculate the time complexity of the listed algorithms, please correct if I'm doing something wrong:
The question is, do some operations like multiplying, dividing, or plus really affect on ...
- 41
1
vote
4
answers
910
views
To what extent is an x86 machine equivalent to a Turing Machine?
To what extent is the abstract model of computation specified by the x86 language Turing complete?
The above question is related to this question: Is C actually Turing-complete?
In theoretical ...
- 87
0
votes
4
answers
632
views
Grammer Class/Production Rules of Programming Languages
I'd read around on the interwebs, and a lot of the text indicated that many programming languages are generated by a context-free grammar, which leads me to 2 questions:
Doesn't variable scoping ...
- 592
2
votes
1
answer
902
views
What was the first Turing-Complete programming language?
What was the first turing-complete language? Know about the first machines
and computers, but not the programming language.
- 23
2
votes
2
answers
150
views
How do we define the term "computation" across models of computation?
How do we define the term computation / computable function generically across models of computation?
Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function&...
- 87