Random thoughts on theoretical Computer Science

I am not a student of Computer Science. [It actually allows me to think shamelessly.]***

Going back to my fascination about boundary conditions, I wonder

  • Why languages create words only ad infinitum? Why can’t there  be “circular” words like “words” representing {“words”, “sword”, “dswor”, “rdswo”, “ordsw”}?
  • Why could not be “next” character bounce back from the end – like bouncing
    • a ball against the wall or
    • walking across North Pole?
  • How would various automatons behave in case of these new definition of “words”? Could a sub-Turing machine suffice?

***

I wonder whether there could be a 2-dimensional formal language – and regular expressions and so on.

Something on the lines of:

ab+c

.+d

should match:

abc

abd

but must not match: (because downwards b+ is not satisfied!)

abc

acd

  • In such cases, I am sure modifiers like “.”,”*”,”?” and “+” will need their two dimensional equivalents.

Like,  in horizontal direction, “.+” could be “>” and “.*” could be “<”

but in vertical direction, “.+” could be “^” and “.*” could be “v” for disambiguation.

  • Are all 2D regular expressions reducible to 1D in some way?
  • I know that a Turing machine with 2D tape is equivalent of a Turing machine. But what about a Turing machine trying to solve a 2D language problem? Will it suffice?
  • If we cross multidimensional language concept with the boundary conditions above, we are likely to end up with a cylindrical language. How would various automatons behave in these circumstances?
Advertisements

2 comments on “Random thoughts on theoretical Computer Science

  1. Yash says:

    If I understand Church Turing thesis, Turing machine solves any and all computable problems, i.e., those problems that cannot be solved by 1D TM are not computable. Either 2D language is not computable, or TM solves it, or else you have found an exception to Church Turing thesis.

    • bhushit says:

      Must be so. Computability and Turing machine are synonymous in my understanding.
      The post is not only about 2D language’s computability. Though I wonder why none talks about 2D language as such. Probably because R^2 is not an ordered field. So “program counters” won’t work.
      The post also wonders about “sub-computability” of some other definitions of a 1-Dlanguage. That is, Turing machine may suffice for a “rolled word” 1-D language but is it necessary? Can some less capable machine also compute all problems in such languages?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s