8 ms·

Arguably impossible for AI, since sufficiently complex language can be Turing complete, and thus general understanding requires solving the halting problem.

by yters 8y ago

melling 8y ago
There’s something in the human brain that can’t be replicated?
- nine_k 8y ago
  When we will have created human-level AI, changes in language translation will likely be a minor detail on the background of other changes in the world.
- ekianjo 8y ago
  Your question sounds like you assume we have a perfect understanding of the brain. At best, our understanding is still very much peripheral. We have no idea how consciousness forms, even if we roughly know where it is located.
  - melling 8y ago
    No, I didn’t assume we have a perfect understanding of the human brain, simply that nothing magical is happening and that we will eventually be able to better understand it.
    - yters 8y ago
      Why don't you think there is something magical happening in the brain?
- frostburg 8y ago
  No, there is no reason to think that the human brain is capable of computing anything that isn't Church-Turing computable. Luckily no translation actually requires a "general solution" of the problem formally.
  - yters 8y ago
    How do you know this is true?
    - frostburg 8y ago
      Texts have finite length.
      - yters 8y ago
        Can you expand the missing premise? 1. Texts have finite length. 2. ____ 3. Therefore, the halting problem does not impact machine translation.
        frostburg 8y ago
        Sorry, missed this. I'll try to explain. A real computer doesn't actually have an infinite tape (memory) like a canonical Turing Machine, it's actually a finite state machine with a vast amount of possible states that we conveniently think about as analogous to a Turing machine, hence the the halting problem is actually solvable (just not in practice) for real hardware. Given content that can be expressed in two languages in a text of finite length, you could in theory enumerate all the possible translated texts.
        yters 8y ago
        If it is not solvable in practice, I don't see how finiteness addresses my objection...
- adrianN 8y ago
  Maybe there are examples of texts that can't be translated even by humans? Language Log has discussions about so-called words that can't be translated regularly and generally rejects that concept, but maybe whole texts are more difficult. The I-Ching has several translations that don't resemble each other very much and it's common knowledge that a translation can be either accurate or beautiful but rarely both.
- yters 8y ago
  If the human mind is non physical, then it is might be a halting oracle.
  - adrianN 8y ago
    If the moon is made of cheese, then 1=2. What does non-physical even mean?
    - yters 8y ago
      It is hard to say what the non-physical is. However, it can be detected. For example, if we could, say, solve the halting problem, then whatever part of us is doing the solving cannot be physical, since everything physical can be computed by a Turing machine. So, in general the non-physical is defined negatively. The physical is defined by physical limitations, i.e. the laws of physics and computation, and thus anything that surpasses those limitations is non-physical.
      - adrianN 8y ago
        There is no algorithm for checking whether a system can solve the halting problem or not, the reduction to the halting problem is quite simple. But that's besides the point. If you found something that could solve the halting problem and you're lucky enough to be able to prove it for this special case, that would just mean that the assumption that everything physical can be computed by a Turing machine is wrong. It works the same way with anything else that we think of as "impossible". If you observed an apple falling towards the sky that doesn't mean that the apple is non-physical, it just points to a serious flaw in our understanding of gravity. Experiments trump all physical theories.
      - yters 8y ago
        That makes the term 'physical' vacuous. Technically, we already recognize the world is non-physical. Materialists defined materialism to things bumping into each other. Now we know there are things like field effects, attraction, and action at a distance. So there is a non-bumping substrate that the bumping things exist within. Thus, strict physicalism is already known to be false.
mistercow 8y ago
If solving the halting problem were necessary to understand language, humans wouldn't be able to understand language either. I think that the confusion here is that you're conflating "comprehension" with "execution". You can write out a set of instructions in English that describe a non-halting algorithm, but I don't have to determine whether the program you've described halts to understand what the algorithm does. And I certainly wouldn't need to determine that in order to translate the instructions into Spanish.
- yters 8y ago
  You assume the human mind is only as powerful as a Turing machine, which is just conjecture. In general, understanding what a program does requires knowing whether it halts. For example, what does this program do when given input another_program? if halts(another_program): print "program halts." else: print "program does not halt."
  - mistercow 8y ago
    >You assume the human mind is only as powerful as a Turing machine, which is just conjecture. Given the lack of any proposals for how, even in theory, hypercomputation might be achieved in a physical system, and the lack of any empirical indication that humans are capable of hypercomputation, I would say it's much more than a conjecture. At the very least, it's an incredibly likely conjecture. > For example, what does this program do when given input another_program? It prints "program halts." if another_program halts, and prints "program does not halt." otherwise. I understand exactly what this program does, even though I can't tell you its output for an arbitrary input. And if I want to translate the above sentence into Spanish, I don't have to come anywhere near solving the halting problem to do so. Consider the following program which does not involve the halting problem: function (targetDigest) i = new BigInt(0); while(true) { if (sha1(i.toBytes()) == targetDigest) { print(i.toBinary()); } i = i.plus(1); } } What does this program do when given targetDigest? It prints out the shortest bit string whose SHA-1 is that targetDigest. I obviously can't tell you what specific answer it will output for a given input, but it would be absurd to say that I don't understand the program. But even if you can come up with sentences that require one to solve the halting problem to translate (and I'm still not convinced such sentences exist), it's another thing entirely to claim that those sentences come up in practice. This is a red herring when it comes to the feasibility of machine translation, because a good translator doesn't need to be able to cope with every valid sentence. It merely needs to cope with the set of sentences that humans actually care about.
deleted 8y ago
[deleted]

Arguably impossible for AI, since sufficiently complex language can be Turing complete, and thus general understanding requires solving the halting problem.

by yters 8y ago

Arguably impossible for AI, since sufficiently complex language can be Turing complete, and thus general understanding requires solving the halting problem.

melling 8y ago

There’s something in the human brain that can’t be replicated?

nine_k 8y ago
When we will have created human-level AI, changes in language translation will likely be a minor detail on the background of other changes in the world.
ekianjo 8y ago
Your question sounds like you assume we have a perfect understanding of the brain. At best, our understanding is still very much peripheral. We have no idea how consciousness forms, even if we roughly know where it is located.
- melling 8y ago
  No, I didn’t assume we have a perfect understanding of the human brain, simply that nothing magical is happening and that we will eventually be able to better understand it.
  - yters 8y ago
    Why don't you think there is something magical happening in the brain?
frostburg 8y ago
No, there is no reason to think that the human brain is capable of computing anything that isn't Church-Turing computable. Luckily no translation actually requires a "general solution" of the problem formally.
- yters 8y ago
  How do you know this is true?
  - frostburg 8y ago
    Texts have finite length.
    - yters 8y ago
      Can you expand the missing premise? 1. Texts have finite length. 2. ____ 3. Therefore, the halting problem does not impact machine translation.
      - frostburg 8y ago
        Sorry, missed this. I'll try to explain. A real computer doesn't actually have an infinite tape (memory) like a canonical Turing Machine, it's actually a finite state machine with a vast amount of possible states that we conveniently think about as analogous to a Turing machine, hence the the halting problem is actually solvable (just not in practice) for real hardware. Given content that can be expressed in two languages in a text of finite length, you could in theory enumerate all the possible translated texts.
        yters 8y ago
        If it is not solvable in practice, I don't see how finiteness addresses my objection...
adrianN 8y ago
Maybe there are examples of texts that can't be translated even by humans? Language Log has discussions about so-called words that can't be translated regularly and generally rejects that concept, but maybe whole texts are more difficult. The I-Ching has several translations that don't resemble each other very much and it's common knowledge that a translation can be either accurate or beautiful but rarely both.
yters 8y ago
If the human mind is non physical, then it is might be a halting oracle.
- adrianN 8y ago
  If the moon is made of cheese, then 1=2. What does non-physical even mean?
  - yters 8y ago
    It is hard to say what the non-physical is. However, it can be detected. For example, if we could, say, solve the halting problem, then whatever part of us is doing the solving cannot be physical, since everything physical can be computed by a Turing machine. So, in general the non-physical is defined negatively. The physical is defined by physical limitations, i.e. the laws of physics and computation, and thus anything that surpasses those limitations is non-physical.
    - adrianN 8y ago
      There is no algorithm for checking whether a system can solve the halting problem or not, the reduction to the halting problem is quite simple. But that's besides the point. If you found something that could solve the halting problem and you're lucky enough to be able to prove it for this special case, that would just mean that the assumption that everything physical can be computed by a Turing machine is wrong. It works the same way with anything else that we think of as "impossible". If you observed an apple falling towards the sky that doesn't mean that the apple is non-physical, it just points to a serious flaw in our understanding of gravity. Experiments trump all physical theories.
    - yters 8y ago
      That makes the term 'physical' vacuous. Technically, we already recognize the world is non-physical. Materialists defined materialism to things bumping into each other. Now we know there are things like field effects, attraction, and action at a distance. So there is a non-bumping substrate that the bumping things exist within. Thus, strict physicalism is already known to be false.

mistercow 8y ago

If solving the halting problem were necessary to understand language, humans wouldn't be able to understand language either. I think that the confusion here is that you're conflating "comprehension" with "execution". You can write out a set of instructions in English that describe a non-halting algorithm, but I don't have to determine whether the program you've described halts to understand what the algorithm does. And I certainly wouldn't need to determine that in order to translate the instructions into Spanish.

yters 8y ago
You assume the human mind is only as powerful as a Turing machine, which is just conjecture. In general, understanding what a program does requires knowing whether it halts. For example, what does this program do when given input another_program? if halts(another_program): print "program halts." else: print "program does not halt."
- mistercow 8y ago
  >You assume the human mind is only as powerful as a Turing machine, which is just conjecture. Given the lack of any proposals for how, even in theory, hypercomputation might be achieved in a physical system, and the lack of any empirical indication that humans are capable of hypercomputation, I would say it's much more than a conjecture. At the very least, it's an incredibly likely conjecture. > For example, what does this program do when given input another_program? It prints "program halts." if another_program halts, and prints "program does not halt." otherwise. I understand exactly what this program does, even though I can't tell you its output for an arbitrary input. And if I want to translate the above sentence into Spanish, I don't have to come anywhere near solving the halting problem to do so. Consider the following program which does not involve the halting problem: function (targetDigest) i = new BigInt(0); while(true) { if (sha1(i.toBytes()) == targetDigest) { print(i.toBinary()); } i = i.plus(1); } } What does this program do when given targetDigest? It prints out the shortest bit string whose SHA-1 is that targetDigest. I obviously can't tell you what specific answer it will output for a given input, but it would be absurd to say that I don't understand the program. But even if you can come up with sentences that require one to solve the halting problem to translate (and I'm still not convinced such sentences exist), it's another thing entirely to claim that those sentences come up in practice. This is a red herring when it comes to the feasibility of machine translation, because a good translator doesn't need to be able to cope with every valid sentence. It merely needs to cope with the set of sentences that humans actually care about.

deleted 8y ago

[deleted]