Questions tagged [philosophy]

35 questions
220
votes
32 answers

Why is writing down mathematical proofs more fault-proof than writing computer code?

I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs. It seems that this is something more widespread than just my experience. Most people make…
user56834
  • 4,294
  • 5
  • 23
  • 36
51
votes
4 answers

Why can humans solve certain "undecidable" problems?

High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation a => b , where a and b are open terms on the simply typed lambda calculus, finds a substitution S such that aS => bS , where => stands…
MaiaVictor
  • 4,287
  • 2
  • 22
  • 35
10
votes
4 answers

Could Gödel’s incompleteness theorem be circumvented with a quine?

As you all probably know, Gödel’s incompleteness theorem states, that it will never be possible for mathematics to prove its own correctness. Mainly because that proof would be part of mathematics too, and hence need proving itself. And that leads…
anon
8
votes
1 answer

Is Coq synthetic or analytic?

In CMU's HoTT course, lecture 1, which can be found here: https://scs.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=0945cc7f-48b7-4803-81af-e7193a3f461d At 33:52, Harper was giving parallel comparison between synthetic theories and analytic ones,…
Jason Hu
  • 652
  • 3
  • 14
8
votes
1 answer

If the Halting Problem was solvable, and we solved it, what would be its implications?

Perhaps a way to better understand the Halting Problem's importance is to know what would happen or what could be possible if this was solved. What would be the Halting Problem's implications in today's technology, mathematics and its practical…
Zaenille
  • 191
  • 1
  • 4
7
votes
2 answers

Solomonoff's theory of induction, Kolmogorov complexity and Bayesian Inference

My motivations for asking this question are philosophical in nature. I'm by no means a computer scientist though, and I feel as though this question should be answered by someone who is since it's one thing to read about a subject second hand and…
Joe Lee-Doktor
  • 171
  • 1
6
votes
2 answers

Quantum computers and computable functions

A quantum computer can possibly calcluate computable functions faster, but it can't calculate functions which a normal computer can't calculate? If a function is not computable? Does this mean it will never be computable? Even if we change the…
user3613886
  • 290
  • 1
  • 8
4
votes
2 answers

If the universe were predetermined, would non-deterministic automata still make sense?

If the universe were governed by predeterminism (i.e. some deity decided in advance how everything, ever, would play out), would the notion of non-deterministic automata make sense? Or would it not, but we wouldn't know it?
JesseTG
  • 325
  • 1
  • 8
4
votes
0 answers

Mathematical explanation and functional pearls

There is a well-established philosophical line of inquiry into mathematical explanation , the idea that, while all sound proofs justify a theorem, some can be more or less (or differently) explanatory. It seems plausible that we can carry over this…
Siddharth
  • 171
  • 2
4
votes
1 answer

Is the Turing machine the only framework to analyse limits of computation?

In Theory of Computation lessons, the limits of computation are usually analyzed within the framework of Turing machines, so if something isn't solvable with Turing Machine, then we consider this problem as undecidable. I know computational models…
math boy
  • 394
  • 1
  • 13
2
votes
1 answer

Algorithms with easily determinable bound on the length of a computation

In the introductory chapter to Theory of Recursive Functions and Effective Computability Rogers discusses what features an informal notion of algorithm should possess. One point he mentions is the question, if we should be able to pre-determine the…
Knogger
  • 2,322
  • 5
  • 16
2
votes
0 answers

What are some of the philosophical implications if BPP = P?

As it stands, the general consensus seems to be that BPP = P. If this conjecture were indeed true, what would be some of the philosophical implications beyond theoretical computer science? I know that the construction of my question is rather fuzzy.…
Ashvin Jagadeesan
  • 31
  • 1
1
vote
1 answer

Can agent be autonomous without having consciousness?

My intuition is that 1) self-awareness (modeled through epistemic modal logics); 2) goal reasoning (e.g. https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12292 ) and 3) consciousness (e.g. Integrated Information Theory) are the necessary…
TomR
  • 1,411
  • 8
  • 17
1
vote
0 answers

is-child-of, is-instance-of as intensional and extensional inheritance relation - is object-oriented modelling an great oversimplification?

I am trying to build knowledge base in OpenCog cognitive architecture ( http://wiki.opencog.org/w/The_Open_Cognition_Project ) and I see that OpenCog lacks usual means to express notions of object-oriented modelling paradigm. E.g. OpenCog has no…
TomR
  • 1,411
  • 8
  • 17
1
vote
1 answer

In the learning theory version of Occam's razor, why can't I just declare whatever hypothesis I want to be "shortest"?

Occam's razor states that shorter explanations (formally speaking, hypotheses) are more likely to be correct. Indeed this can be formalized: for a hypothesis class $\mathcal H$ one may ascribe representations to each hypothesis and take their…
djechlin
  • 497
  • 4
  • 15
1
2 3